<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1,user-scalable=no"><title>大学课程 | 《算法分析与设计》笔记 | Justlovesmile's BLOG</title><meta name="keywords" content="算法,学习笔记,大学课程"><meta name="author" content="Justlovesmile,865717150@qq.com"><meta name="copyright" content="Justlovesmile"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="大三算法设计与分析笔记总结与知识点整理"><meta property="og:type" content="article"><meta property="og:title" content="大学课程 | 《算法分析与设计》笔记"><meta property="og:url" content="https://blog.justlovesmile.top/posts/16050.html"><meta property="og:site_name" content="Justlovesmile&#39;s BLOG"><meta property="og:description" content="大三算法设计与分析笔记总结与知识点整理"><meta property="og:locale" content="zh_CN"><meta property="og:image" content="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/H21b5f6b8496141a1979a33666e1074d9x.jpg"><meta property="article:published_time" content="2019-11-19T13:19:57.000Z"><meta property="article:modified_time" content="2019-11-19T13:19:57.000Z"><meta property="article:author" content="Justlovesmile"><meta property="article:tag" content="算法"><meta property="article:tag" content="学习笔记"><meta property="article:tag" content="大学课程"><meta name="twitter:card" content="summary"><meta name="twitter:image" content="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/H21b5f6b8496141a1979a33666e1074d9x.jpg"><link rel="shortcut icon" href="/img/logo.jpg"><link rel="canonical" href="https://blog.justlovesmile.top/posts/16050"><link rel="preconnect" href="//cdn.jsdelivr.net"><link rel="preconnect" href="//hm.baidu.com"><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.css" media="print" onload='this.media="all"'><script>var _hmt=_hmt||[];!function(){var e=document.createElement("script");e.src="https://hm.baidu.com/hm.js?a2ee893562999ebad688b0d82daa100a";var t=document.getElementsByTagName("script")[0];t.parentNode.insertBefore(e,t)}()</script><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/font/family=Titillium+Web.css" media="print" onload='this.media="all"'><script>const GLOBAL_CONFIG={root:"/",algolia:void 0,localSearch:{path:"search.xml",languages:{hits_empty:"找不到您查询的内容：${query}"}},translate:void 0,noticeOutdate:void 0,highlight:{plugin:"highlighjs",highlightCopy:!0,highlightLang:!0,highlightHeightLimit:400},copy:{success:"复制成功",error:"复制错误",noSupport:"浏览器不支持"},relativeDate:{homepage:!1,post:!1},runtime:"天",date_suffix:{just:"刚刚",min:"分钟前",hour:"小时前",day:"天前",month:"个月前"},copyright:{limitCount:100,languages:{author:"作者: Justlovesmile",link:"链接: ",source:"来源: Justlovesmile's BLOG",info:"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},lightbox:"fancybox",Snackbar:{chs_to_cht:"你已切换为繁体",cht_to_chs:"你已切换为简体",day_to_night:"你已切换为深色模式",night_to_day:"你已切换为浅色模式",bgLight:"var(--mj-card-bg)",bgDark:"var(--mj-card-bg)",position:"top-right"},source:{justifiedGallery:{js:"https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.js",css:"https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.css"}},isPhotoFigcaption:!1,islazyload:!0,isAnchor:!1}</script><script id="config-diff">var GLOBAL_CONFIG_SITE={title:"大学课程 | 《算法分析与设计》笔记",isPost:!0,isHome:!1,isHighlightShrink:!1,isToc:!0,postUpdate:"2019-11-19 21:19:57"}</script><noscript><style>#nav{opacity:1}.justified-gallery img{opacity:1}#post-meta time,#recent-posts time{display:inline!important}</style></noscript><script>(e=>{e.saveToLocal={set:function(e,t,o){if(0===o)return;const a=864e5*o,n={value:t,expiry:(new Date).getTime()+a};localStorage.setItem(e,JSON.stringify(n))},get:function(e){const t=localStorage.getItem(e);if(!t)return;const o=JSON.parse(t);if(!((new Date).getTime()>o.expiry))return o.value;localStorage.removeItem(e)}},e.getScript=e=>new Promise((t,o)=>{const a=document.createElement("script");a.src=e,a.async=!0,a.onerror=o,a.onload=a.onreadystatechange=function(){const e=this.readyState;e&&"loaded"!==e&&"complete"!==e||(a.onload=a.onreadystatechange=null,t())},document.head.appendChild(a)}),e.activateDarkMode=function(){document.documentElement.setAttribute("data-theme","dark"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#0d0d0d")},e.activateLightMode=function(){document.documentElement.setAttribute("data-theme","light"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#ffffff")};const t=saveToLocal.get("theme"),o=(new Date).getHours();void 0===t?o<=6||o>=18?activateDarkMode():activateLightMode():"light"===t?activateLightMode():activateDarkMode();/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)&&document.documentElement.classList.add("apple")})(window)</script><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome@4.7.0/css/font-awesome.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/font-awesome-animation@0.2.1/dist/font-awesome-animation.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/swiper/swiper-bundle.min.css"><link rel="stylesheet" href="/css/justlovesmile.css"><link rel="stylesheet" href="/css/blogicon.css"><meta name="generator" content="Hexo 5.4.0"><link rel="alternate" href="/atom.xml" title="Justlovesmile's BLOG" type="application/atom+xml"></head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="" data-lazy-src="/img/avatar.jpg" onerror='onerror=null,src="/img/friend_404.gif"' alt="avatar"></div><div class="site-data is-center"><div class="data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">75</div></a></div><div class="data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">69</div></a></div><div class="data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">6</div></a></div></div><hr><div class="menus_items"><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>网站</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/"><i class="fa-fw fas fa-home"></i> <span>首页</span></a></li><li><a class="site-page child" href="/guestbook/"><i class="fa-fw fas fa-pencil-alt"></i> <span>留言</span></a></li><li><a class="site-page child" href="/friends/"><i class="fa-fw fas fa-paper-plane"></i> <span>友链</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>文库</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i> <span>全部标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i> <span>全部分类</span></a></li><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-calendar"></i> <span>文章列表</span></a></li><li><a class="site-page child" href="/random/"><i class="fa-fw fas fa-shoe-prints"></i> <span>随便逛逛</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>实验室</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/laboratory/"><i class="fa-fw fa fa-lightbulb-o"></i> <span>项目展示</span></a></li><li><a class="site-page child" href="/fcircle/"><i class="fa-fw fa fa-puzzle-piece"></i> <span>友链订阅</span></a></li><li><a class="site-page child" href="/charts/"><i class="fa-fw fa fa-pie-chart"></i> <span>博客统计</span></a></li><li><a class="site-page child" href="/update/"><i class="fa-fw fa fa-commenting-o"></i> <span>更新日志</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>清单</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/photos/"><i class="fa-fw fas fa-camera-retro"></i> <span>相册</span></a></li><li><a class="site-page child" href="/video/"><i class="fa-fw fa fa-video-camera"></i> <span>视频</span></a></li><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i> <span>歌单</span></a></li><li><a class="site-page child" href="/focus/"><i class="fa-fw fa fa-check-square-o"></i> <span>关注</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>关于</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/about/"><i class="fa-fw fas fa-user"></i> <span>本站</span></a></li><li><a class="site-page child" href="/love/"><i class="fa-fw fa fa-heart"></i> <span>Love</span></a></li><li><a class="site-page child" href="/donate/"><i class="fa-fw fa fa-gratipay"></i> <span>打赏</span></a></li></ul></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image:url(https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/H21b5f6b8496141a1979a33666e1074d9x.jpg)"><nav id="nav"><div id="nav-group"><div id="blog_name"><a id="site-name" href="/">Justlovesmile</a></div><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>网站</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/"><i class="fa-fw fas fa-home"></i> <span>首页</span></a></li><li><a class="site-page child" href="/guestbook/"><i class="fa-fw fas fa-pencil-alt"></i> <span>留言</span></a></li><li><a class="site-page child" href="/friends/"><i class="fa-fw fas fa-paper-plane"></i> <span>友链</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>文库</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i> <span>全部标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i> <span>全部分类</span></a></li><li><a class="site-page child" href="/archives/"><i class="fa-fw fas fa-calendar"></i> <span>文章列表</span></a></li><li><a class="site-page child" href="/random/"><i class="fa-fw fas fa-shoe-prints"></i> <span>随便逛逛</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>实验室</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/laboratory/"><i class="fa-fw fa fa-lightbulb-o"></i> <span>项目展示</span></a></li><li><a class="site-page child" href="/fcircle/"><i class="fa-fw fa fa-puzzle-piece"></i> <span>友链订阅</span></a></li><li><a class="site-page child" href="/charts/"><i class="fa-fw fa fa-pie-chart"></i> <span>博客统计</span></a></li><li><a class="site-page child" href="/update/"><i class="fa-fw fa fa-commenting-o"></i> <span>更新日志</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>清单</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/photos/"><i class="fa-fw fas fa-camera-retro"></i> <span>相册</span></a></li><li><a class="site-page child" href="/video/"><i class="fa-fw fa fa-video-camera"></i> <span>视频</span></a></li><li><a class="site-page child" href="/music/"><i class="fa-fw fas fa-music"></i> <span>歌单</span></a></li><li><a class="site-page child" href="/focus/"><i class="fa-fw fa fa-check-square-o"></i> <span>关注</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><span>关于</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/about/"><i class="fa-fw fas fa-user"></i> <span>本站</span></a></li><li><a class="site-page child" href="/love/"><i class="fa-fw fa fa-heart"></i> <span>Love</span></a></li><li><a class="site-page child" href="/donate/"><i class="fa-fw fa fa-gratipay"></i> <span>打赏</span></a></li></ul></div></div></div><div id="nav-right"><div id="search-button"><a class="nav-rightbutton site-page social-icon search"><i class="fas fa-search fa-fw"></i></a></div><div id="darkmode_navswitch"><a class="nav-rightbutton site-page darkmode_switchbutton" onclick="switchDarkMode()"><i class="fas fa-adjust"></i></a></div><div id="toggle-menu"><a class="nav-rightbutton site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></div></nav><div class="coverdiv" id="coverdiv"><img class="cover entered loading" id="post-cover" alt="cover" src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/H21b5f6b8496141a1979a33666e1074d9x.jpg"></div><div id="post-info"><div class="post-firstinfo" id="post-meta"><span class="post-meta-categories"><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a></span><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E7%AE%97%E6%B3%95/">#算法</a><a class="post-meta__tags" href="/tags/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">#学习笔记</a><a class="post-meta__tags" href="/tags/%E5%A4%A7%E5%AD%A6%E8%AF%BE%E7%A8%8B/">#大学课程</a></div></div><h1 class="post-title">大学课程 | 《算法分析与设计》笔记</h1><div id="post-meta"><div class="meta-firstline"><span class="meta-share-time"><span class="meta-avatar"><a class="meta-avatar-img" href="/about/" title="关于作者"><img alt="作者头像" src="" data-lazy-src="/img/avatar.jpg"></a><a class="meta-avatar-name" href="/about/" title="关于作者">Justlovesmile</a></span></span><span class="post-meta-date"><i class="fa-fw post-meta-icon far fa-calendar-alt"></i><span class="post-meta-label">发表于</span><time datetime="2019-11-19T13:19:57.000Z" title="发表于 2019-11-19 21:19:57">2019-11-19</time></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">14k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>62分钟</span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><p>大三算法设计与分析笔记总结与知识点整理</p><span id="more"></span><h1 style="text-align:center">笔记总结</h1><h1 id="第一章-算法引论"><a href="#第一章-算法引论" class="headerlink" title="第一章 算法引论"></a>第一章 算法引论</h1><h2 id="1-1-算法与程序"><a href="#1-1-算法与程序" class="headerlink" title="1.1 算法与程序"></a>1.1 算法与程序</h2><ul><li>算法定义：解决问题的方法或过程</li><li>算法的性质：<ul><li>（1）输入：有零个或多个外部量作为算法的输入</li><li>（2）输出：算法产生至少一个量作为输出</li><li>（3）确定性：组成算法的每条指令是清晰的，无歧义的</li><li>（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限</li><li>有时还会加入通用性或可行性</li></ul></li><li>程序的定义：是算法用某种程序设计语言的具体实现。</li><li>程序与算法的区别：程序可以不满足算法的第四点性质即有限性。例如操作系统，是在无限循环中执行的程序。</li></ul><h2 id="1-2-表达算法的抽象机制"><a href="#1-2-表达算法的抽象机制" class="headerlink" title="1.2 表达算法的抽象机制"></a>1.2 表达算法的抽象机制</h2><ul><li>为了将顶层算法与底层算法隔开，使二者在设计时不互相牵制，互相影响，必须对二者的接口进行抽象。让底层只通过接口为顶层服务，顶层也只通过接口调用底层运算。这个接口就是<strong>抽象数据类型</strong>(ADT)。</li></ul><h2 id="1-3-描述算法"><a href="#1-3-描述算法" class="headerlink" title="1.3 描述算法"></a>1.3 描述算法</h2><ul><li>有多种方式，如：自然语言方式，表格方式，高级程序语言方式等…</li></ul><h2 id="1-4-算法复杂性分析"><a href="#1-4-算法复杂性分析" class="headerlink" title="1.4 算法复杂性分析"></a>1.4 算法复杂性分析</h2><ul><li>算法分析的目的：分析算法占用计算机资源的情况，对算法做出比较和评价，设计出更好的算法</li><li>算法的复杂性是算法运行时所需的计算机资源的量，需要时间资源的量称为<strong>时间复杂性</strong>，需要空间资源的量称为<strong>空间复杂性</strong>。</li><li>C=F(N,I,A)，用N，I，A分别表示算法要解的问题的规模，算法的输入和算法本身，F表示是上诉N，I，A的确定的三元函数，C表示复杂性</li><li>一般只考虑3种情况下的时间复杂性，即最坏情况，最好情况，平均情况</li><li>实践表明，可操作性最好且最有实际价值的是<strong>最坏情况下的时间复杂性</strong>。</li><li>复杂性渐进性态：<figure class="highlight excel"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">对于<span class="built_in">T</span>(<span class="built_in">N</span>)，如果存在~<span class="built_in">T</span>(<span class="built_in">N</span>)，使得当<span class="built_in">N</span>→∞时有(<span class="built_in">T</span>(<span class="built_in">N</span>)-~<span class="built_in">T</span>(<span class="built_in">N</span>))/<span class="built_in">T</span>(<span class="built_in">N</span>)→<span class="number">0</span>，那么就说~<span class="built_in">T</span>(<span class="built_in">N</span>)是<span class="built_in">T</span>(<span class="built_in">N</span>)当<span class="built_in">N</span>→∞时的渐进性态。</span><br></pre></td></tr></table></figure></li><li>如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。这时还说f(N)的阶不高于g(N)的阶。</li><li>对于符号O，有如下运算规则：<ul><li>O(f)+O(g)=O(max(f,g))</li><li>O(f)+O(g)=O(f+g)</li><li>O(f)O(g)=O(fg)</li><li>如果g(N)=O(f(N)),则O(f)+O(g)=O(f)</li><li>O(Cf(N))=O(f(N)),其中C是一个正的常数</li><li>f=O(f)</li></ul></li></ul><h1 id="第二章-递归与分治策略"><a href="#第二章-递归与分治策略" class="headerlink" title="第二章 递归与分治策略"></a>第二章 递归与分治策略</h1><h2 id="2-1-递归的概念"><a href="#2-1-递归的概念" class="headerlink" title="2.1 递归的概念"></a>2.1 递归的概念</h2><ul><li><p>直接或间接地调用自身的算法称为<strong>递归算法</strong>。用函数自身给出定义的函数称为<code>递归函数</code></p></li><li><p>递归函数的两个要素：<code>边界条件</code>和<code>递归方程</code></p></li><li><p>阶乘函数：</p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">factorial</span><span class="params">(<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">0</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> n*<span class="built_in">factorial</span>(n<span class="number">-1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></li><li><p>Fibonacci数列：</p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">fibonacci</span><span class="params">(<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(n&lt;=<span class="number">1</span>) <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">return</span> <span class="built_in">fibonacci</span>(n<span class="number">-1</span>)+<span class="built_in">fibonacci</span>(n<span class="number">-2</span>);</span><br><span class="line">&#125; </span><br></pre></td></tr></table></figure></li><li><p>hanoi塔：</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">hanoi</span>(<span class="params">n,a,b,c</span>):</span></span><br><span class="line">    <span class="comment">#将a上的n个圆盘经过c移动到b</span></span><br><span class="line">    <span class="keyword">if</span>(n&gt;<span class="number">0</span>):</span><br><span class="line">        hanoi(n-<span class="number">1</span>,a,c,b)</span><br><span class="line">        move(a,b)</span><br><span class="line">        hanoi(n-<span class="number">1</span>,c,b,a)</span><br></pre></td></tr></table></figure></li><li><p>递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性</p></li><li><p>递归算法的缺点：运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法多。</p></li><li><p>消除递归的方法：①采用一个用户定义的栈来模拟系统的递归调用工作栈，从而达到将递归算法改为非递归算法的目的②用递推来实现递归函数</p></li></ul><h2 id="2-2-分治法的基本思想"><a href="#2-2-分治法的基本思想" class="headerlink" title="2.2 分治法的基本思想"></a>2.2 分治法的基本思想</h2><ul><li>分治法的基本思想：将一个规模为n的问题<code>分解</code>为k个规模较小的子问题，这些子问题<code>相互独立</code>且与原问题<code>相同</code>。递归地解这些子问题，然后将各子问题的解<code>合并</code>得到原问题的解。</li><li>分治法的适用条件：<ul><li>①该问题的规模缩小到一定程度容易解决。</li><li>②该问题可以分解为若干个规模较小的相同问题。即该问题具有最优子结构性质。</li><li>③该问题分解出的子问题的解可以合并为该问题的解。</li><li>④子问题间不包含公共的子问题（各子问题相互独立）</li></ul></li><li>分治法的步骤：<ul><li>划分</li><li>解决</li><li>合并</li></ul></li></ul><h2 id="2-3-二分搜索技术"><a href="#2-3-二分搜索技术" class="headerlink" title="2.3 二分搜索技术"></a>2.3 二分搜索技术</h2><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">binarySearch</span>(<span class="params">a,x</span>):</span></span><br><span class="line">	<span class="comment">#a是数组,x是要搜索的数</span></span><br><span class="line">	a=<span class="built_in">sorted</span>(a)</span><br><span class="line">	<span class="comment">#a要求有序（从小到大）</span></span><br><span class="line">	n=<span class="built_in">len</span>(a)</span><br><span class="line">	left,right=<span class="number">0</span>,n-<span class="number">1</span></span><br><span class="line">	<span class="keyword">while</span>(left&lt;=right):</span><br><span class="line">		middle=(left+right)//<span class="number">2</span></span><br><span class="line">		<span class="keyword">if</span>(x==a[middle]):</span><br><span class="line">			<span class="keyword">return</span> middle</span><br><span class="line">		<span class="keyword">elif</span>(x&gt;a[middle]):</span><br><span class="line">			left=middle+<span class="number">1</span></span><br><span class="line">		<span class="keyword">else</span>:</span><br><span class="line">			right=middle-<span class="number">1</span></span><br><span class="line">	<span class="comment">#未找到</span></span><br><span class="line">	<span class="keyword">return</span> -<span class="number">1</span></span><br></pre></td></tr></table></figure><ul><li>最坏情况下，时间复杂度是O(logn)</li></ul><h2 id="2-4-大整数乘法"><a href="#2-4-大整数乘法" class="headerlink" title="2.4 大整数乘法"></a>2.4 大整数乘法</h2><ul><li>设x和y都是n位的二进制整数，现在要计算他们的乘积xy。如果直接相乘，需要O(n^2)步，而其分治法是：将n位二进制整数X和Y都分为2段，每段的长为n/2位：<figure class="highlight mathematica"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="variable">X</span><span class="operator">=</span><span class="punctuation">[</span><span class="variable">A</span><span class="punctuation">]</span><span class="punctuation">[</span><span class="variable">B</span><span class="punctuation">]</span><span class="operator">,</span><span class="variable">Y</span><span class="operator">=</span><span class="punctuation">[</span><span class="built_in">C</span><span class="punctuation">]</span><span class="punctuation">[</span><span class="built_in">D</span><span class="punctuation">]</span><span class="operator">,</span>其中<span class="variable">X</span>，<span class="variable">Y</span>有<span class="variable">n</span>位；<span class="variable">A</span>，<span class="variable">B</span>，<span class="built_in">C</span>，<span class="built_in">D</span>均有<span class="variable">n</span><span class="operator">/</span><span class="number">2</span>位</span><br><span class="line">由此可以得到：</span><br><span class="line"><span class="variable">X</span><span class="operator">=</span><span class="variable">A</span><span class="operator">*</span><span class="number">2</span><span class="operator">^</span><span class="punctuation">(</span><span class="variable">n</span><span class="operator">/</span><span class="number">2</span><span class="punctuation">)</span><span class="operator">+</span><span class="variable">B</span> <span class="operator">,</span> <span class="variable">Y</span><span class="operator">=</span><span class="built_in">C</span><span class="operator">*</span><span class="number">2</span><span class="operator">^</span><span class="punctuation">(</span><span class="variable">n</span><span class="operator">/</span><span class="number">2</span><span class="punctuation">)</span><span class="operator">+</span><span class="built_in">D</span></span><br><span class="line"></span><br><span class="line"><span class="variable">XY</span><span class="operator">=</span><span class="punctuation">(</span><span class="variable">A</span><span class="operator">*</span><span class="number">2</span><span class="operator">^</span><span class="punctuation">(</span><span class="variable">n</span><span class="operator">/</span><span class="number">2</span><span class="punctuation">)</span><span class="operator">+</span><span class="variable">B</span><span class="punctuation">)</span><span class="punctuation">(</span><span class="built_in">C</span><span class="operator">*</span><span class="number">2</span><span class="operator">^</span><span class="punctuation">(</span><span class="variable">n</span><span class="operator">/</span><span class="number">2</span><span class="punctuation">)</span><span class="operator">+</span><span class="built_in">D</span><span class="punctuation">)</span></span><br><span class="line">  <span class="operator">=</span><span class="variable">A</span><span class="operator">*</span><span class="built_in">C</span><span class="operator">*</span><span class="number">2</span><span class="operator">^</span><span class="variable">n</span><span class="operator">+</span><span class="punctuation">(</span><span class="variable">A</span><span class="operator">*</span><span class="built_in">D</span><span class="operator">+</span><span class="built_in">C</span><span class="operator">*</span><span class="variable">B</span><span class="punctuation">)</span><span class="operator">*</span><span class="number">2</span><span class="operator">^</span><span class="punctuation">(</span><span class="variable">n</span><span class="operator">/</span><span class="number">2</span><span class="punctuation">)</span><span class="operator">+</span><span class="variable">B</span><span class="operator">*</span><span class="built_in">D</span></span><br><span class="line">  <span class="operator">=</span><span class="variable">A</span><span class="operator">*</span><span class="built_in">C</span><span class="operator">*</span><span class="number">2</span><span class="operator">^</span><span class="variable">n</span><span class="operator">+</span><span class="punctuation">(</span><span class="punctuation">(</span><span class="variable">A</span><span class="operator">-</span><span class="variable">B</span><span class="punctuation">)</span><span class="punctuation">(</span><span class="built_in">D</span><span class="operator">-</span><span class="built_in">C</span><span class="punctuation">)</span><span class="operator">+</span><span class="variable">A</span><span class="operator">*</span><span class="built_in">C</span><span class="operator">+</span><span class="variable">B</span><span class="operator">*</span><span class="built_in">D</span><span class="punctuation">)</span><span class="operator">*</span><span class="number">2</span><span class="operator">^</span><span class="punctuation">(</span><span class="variable">n</span><span class="operator">/</span><span class="number">2</span><span class="punctuation">)</span><span class="operator">+</span><span class="variable">B</span><span class="operator">*</span><span class="built_in">D</span></span><br><span class="line"></span><br><span class="line">最后一个式子看起来似乎复杂了，但是它仅需做<span class="number">3</span>次<span class="variable">n</span><span class="operator">/</span><span class="number">2</span>位整数的乘法，<span class="number">6</span>次加减法和<span class="number">2</span>次移位</span><br></pre></td></tr></table></figure></li></ul><h2 id="2-5-Strassen矩阵乘法"><a href="#2-5-Strassen矩阵乘法" class="headerlink" title="2.5 Strassen矩阵乘法"></a>2.5 Strassen矩阵乘法</h2><ul><li>对于方阵（n*n）A,B,C，有C=A*B,将它们都分块成4个大小相等的子矩阵，每个子矩阵都是<code>(n/2)*(n/2)</code>的方阵</li><li><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/20/MhaKxS.png" alt="MhaKxS.png"></li></ul><h2 id="2-7-合并排序"><a href="#2-7-合并排序" class="headerlink" title="2.7 合并排序"></a>2.7 合并排序</h2><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">merge</span>(<span class="params">arr,left,mid,right</span>):</span></span><br><span class="line">    <span class="comment">#left，right为需要合并的数组范围</span></span><br><span class="line">    <span class="comment">#mid为中间下标，左边比中值小，右边比中值大</span></span><br><span class="line">    i=left</span><br><span class="line">    j=mid+<span class="number">1</span></span><br><span class="line">    <span class="comment">#复制一个临时数组</span></span><br><span class="line">    aux=arr[:]</span><br><span class="line">    <span class="keyword">for</span> k <span class="keyword">in</span> <span class="built_in">range</span>(left,right+<span class="number">1</span>):</span><br><span class="line">        <span class="comment">#如果左指针超过mid，即右边还有剩余</span></span><br><span class="line">        <span class="keyword">if</span>(i&gt;mid):</span><br><span class="line">            arr[k]=aux[j]</span><br><span class="line">            j=j+<span class="number">1</span></span><br><span class="line">        <span class="comment">#如果右指针超过right，即左边还有剩余</span></span><br><span class="line">        <span class="keyword">elif</span>(j&gt;right):</span><br><span class="line">            arr[k]=aux[i]</span><br><span class="line">            i=i+<span class="number">1</span></span><br><span class="line">        <span class="comment">#如果左边小，则左边合并</span></span><br><span class="line">        <span class="keyword">elif</span>(aux[i]&lt;aux[j]):</span><br><span class="line">            arr[k]=aux[i]</span><br><span class="line">            i=i+<span class="number">1</span></span><br><span class="line">        <span class="comment">#如果右边小</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            arr[k]=aux[j]</span><br><span class="line">            j=j+<span class="number">1</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">mergeSort</span>(<span class="params">arr,left,right</span>):</span></span><br><span class="line">    <span class="comment">#如果已经遍历完</span></span><br><span class="line">    <span class="keyword">if</span>(left&gt;=right):</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="comment">#取中值，拆成左右两边</span></span><br><span class="line">    mid=(left+right)//<span class="number">2</span></span><br><span class="line">    <span class="comment">#对左半边进行归并排序</span></span><br><span class="line">    mergeSort(arr,left,mid)</span><br><span class="line">    <span class="comment">#对右半边进行归并排序</span></span><br><span class="line">    mergeSort(arr,mid+<span class="number">1</span>,right)</span><br><span class="line">    <span class="comment">#合并算法</span></span><br><span class="line">    merge(arr,left,mid,right)</span><br></pre></td></tr></table></figure><ul><li>最坏情况下的时间复杂度为O(nlogn)</li></ul><h2 id="2-8-快速排序"><a href="#2-8-快速排序" class="headerlink" title="2.8 快速排序"></a>2.8 快速排序</h2><ul><li><p>步骤：分解，递归求解，合并</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">quicksort</span>(<span class="params">arr,low,high</span>):</span></span><br><span class="line">    <span class="keyword">if</span> low&lt;high :</span><br><span class="line">        index=getindex(arr,low,high)</span><br><span class="line">        quicksort(arr,low,index-<span class="number">1</span>)</span><br><span class="line">        quicksort(arr,index+<span class="number">1</span>,high)</span><br><span class="line"></span><br><span class="line"><span class="comment">#快速排序算法核心</span></span><br><span class="line"><span class="comment">#作用：将小于基准值的数放在其左边，大于在右边</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">getindex</span>(<span class="params">arr,low,high</span>):</span></span><br><span class="line">    <span class="comment">#默认第一个数字为标准值</span></span><br><span class="line">    temp=arr[low]</span><br><span class="line">    <span class="comment">#当未遍历完，即左右指针未相遇</span></span><br><span class="line">    <span class="keyword">while</span>(low&lt;high):</span><br><span class="line">        <span class="comment">#如果右边大于标准值，右指针左移</span></span><br><span class="line">        <span class="keyword">while</span>((low&lt;high)<span class="keyword">and</span>(arr[high]&gt;=temp)):</span><br><span class="line">            high=high-<span class="number">1</span></span><br><span class="line">        <span class="comment">#此时右指针对应值小于标准值，将其复制给左指针位置</span></span><br><span class="line">        arr[low]=arr[high]</span><br><span class="line">        <span class="comment">#当左边小于标准值，左指针右移</span></span><br><span class="line">        <span class="keyword">while</span>((low&lt;high)<span class="keyword">and</span>(arr[low]&lt;=temp)):</span><br><span class="line">            low=low+<span class="number">1</span></span><br><span class="line">        <span class="comment">#此时左指针对应值大于标准值，将其复制给右指针位置</span></span><br><span class="line">        arr[high]=arr[low]</span><br><span class="line">    <span class="comment">#将标准值赋值给左右指针相遇的位置</span></span><br><span class="line">    arr[low]=temp</span><br><span class="line">    <span class="comment">#此时low左边全部小于等于arr[low],low右边全部大于等于arr[low]</span></span><br><span class="line">    <span class="keyword">return</span> low</span><br></pre></td></tr></table></figure></li><li><p>快排平均情况下的时间复杂度是O(nlogn)，最坏情况下的时间复杂度是O(n^2)</p></li></ul><h2 id="2-9-线性时间选择"><a href="#2-9-线性时间选择" class="headerlink" title="2.9 线性时间选择"></a>2.9 线性时间选择</h2><ul><li>找出一组数中，第X大（小）的数</li><li>采用了随机划分算法</li></ul><h2 id="2-10-最近点对问题"><a href="#2-10-最近点对问题" class="headerlink" title="2.10 最近点对问题"></a>2.10 最近点对问题</h2><ul><li>时间复杂度分析O(nlogn)</li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 最近点对问题</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#按x坐标排序的点</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Point1</span>:</span></span><br><span class="line">    <span class="comment">#x,y为坐标，id为序号</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,xx,yy,index</span>):</span></span><br><span class="line">        self.x=xx</span><br><span class="line">        self.y=yy</span><br><span class="line">        self.<span class="built_in">id</span>=index</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">#按y坐标排序的点</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Point2</span>(<span class="params">Point1</span>):</span></span><br><span class="line">    <span class="comment">#x，y为坐标，id为该点按x排序时的序号</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,xx,yy,index</span>):</span></span><br><span class="line">        self.x=xx</span><br><span class="line">        self.y=yy</span><br><span class="line">        self.<span class="built_in">id</span>=index</span><br><span class="line">        </span><br><span class="line"><span class="comment">#表示输出的平面点对</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Pair</span>:</span></span><br><span class="line">    <span class="comment">#a，b为点，dist为距离</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self, aa, bb,dd</span>):</span></span><br><span class="line">        self.a=aa</span><br><span class="line">        self.b=bb</span><br><span class="line">        self.dist=dd</span><br><span class="line">    </span><br><span class="line"><span class="comment">#求平面上任意两点u,v的距离</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">dist</span>(<span class="params">u,v</span>):</span></span><br><span class="line">    dx=u.x-v.x</span><br><span class="line">    dy=u.y-v.y</span><br><span class="line">    <span class="keyword">return</span> dx*dx+dy*dy</span><br><span class="line"></span><br><span class="line"><span class="comment">#归并排序</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">merge</span>(<span class="params">S,order,left,mid,right</span>):</span></span><br><span class="line">    i=left</span><br><span class="line">    j=mid+<span class="number">1</span></span><br><span class="line">    aux=S[:]</span><br><span class="line">    <span class="comment">#按x排序</span></span><br><span class="line">    <span class="keyword">if</span>(order==<span class="string">&#x27;x&#x27;</span>):</span><br><span class="line">        <span class="keyword">for</span> k <span class="keyword">in</span> <span class="built_in">range</span>(left,right+<span class="number">1</span>):</span><br><span class="line">            <span class="keyword">if</span>(i&gt;mid):</span><br><span class="line">                S[k]=aux[j]</span><br><span class="line">                j=j+<span class="number">1</span></span><br><span class="line">            <span class="keyword">elif</span>(j&gt;right):</span><br><span class="line">                S[k]=aux[i]</span><br><span class="line">                i=i+<span class="number">1</span></span><br><span class="line">            <span class="keyword">elif</span>(S[i].x&lt;aux[j].x):</span><br><span class="line">                S[k]=aux[i]</span><br><span class="line">                i=i+<span class="number">1</span></span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                S[k]=aux[j]</span><br><span class="line">                j=j+<span class="number">1</span></span><br><span class="line">    <span class="comment">#按y排序</span></span><br><span class="line">    <span class="keyword">elif</span>(order==<span class="string">&#x27;y&#x27;</span>):</span><br><span class="line">        <span class="keyword">for</span> k <span class="keyword">in</span> <span class="built_in">range</span>(left,right+<span class="number">1</span>):</span><br><span class="line">            <span class="keyword">if</span>(i&gt;mid):</span><br><span class="line">                S[k]=aux[j]</span><br><span class="line">                j=j+<span class="number">1</span></span><br><span class="line">            <span class="keyword">elif</span>(j&gt;right):</span><br><span class="line">                S[k]=aux[i]</span><br><span class="line">                i=i+<span class="number">1</span></span><br><span class="line">            <span class="keyword">elif</span>(S[i].y&lt;aux[j].y):</span><br><span class="line">                S[k]=aux[i]</span><br><span class="line">                i=i+<span class="number">1</span></span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                S[k]=aux[j]</span><br><span class="line">                j=j+<span class="number">1</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#归并排序</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">mergeSort</span>(<span class="params">S,x,left,right</span>):</span></span><br><span class="line">    <span class="keyword">if</span>(left&gt;=right):</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    mid=(left+right)//<span class="number">2</span></span><br><span class="line">    mergeSort(S,x,left,mid)</span><br><span class="line">    mergeSort(S,x,mid+<span class="number">1</span>,right)</span><br><span class="line">    merge(S,x,left,mid,right)</span><br><span class="line"></span><br><span class="line"><span class="comment">#计算最接近点对</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">closePair</span>(<span class="params">S,Y,Z,l,r</span>):</span></span><br><span class="line">    <span class="comment">#两个点</span></span><br><span class="line">    <span class="keyword">if</span>(r-l==<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">return</span> Pair(S[l],S[r],dist(S[l],S[r]))</span><br><span class="line">    <span class="comment">#三个点</span></span><br><span class="line">    <span class="keyword">if</span>(r-l==<span class="number">2</span>):</span><br><span class="line">        d1=dist(S[l],S[l+<span class="number">1</span>])</span><br><span class="line">        d2=dist(S[l+<span class="number">1</span>],S[r])</span><br><span class="line">        d3=dist(S[l],S[r])</span><br><span class="line">        <span class="keyword">if</span>((d1&lt;=d2)<span class="keyword">and</span>(d1&lt;=d3)):</span><br><span class="line">            <span class="keyword">return</span> Pair(S[l],S[l+<span class="number">1</span>],d1)</span><br><span class="line">        <span class="keyword">if</span>(d2&lt;=d3):</span><br><span class="line">            <span class="keyword">return</span> Pair(S[l+<span class="number">1</span>],S[r],d2)</span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            <span class="keyword">return</span> Pair(S[l],S[r],d3)</span><br><span class="line">    <span class="comment">#多于三个点</span></span><br><span class="line">    m=(l+r)//<span class="number">2</span></span><br><span class="line">    f=l</span><br><span class="line">    g=m+<span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(l,r+<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">if</span>(Y[i].<span class="built_in">id</span>&gt;m):</span><br><span class="line">            Z[g]=Y[i] </span><br><span class="line">            g=g+<span class="number">1</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            Z[f]=Y[i]</span><br><span class="line">            f=f+<span class="number">1</span></span><br><span class="line">    <span class="comment">#递归求解</span></span><br><span class="line">    best = closePair(S,Z,Y,l,m)</span><br><span class="line">    right = closePair(S,Z,Y,m+<span class="number">1</span>,r)</span><br><span class="line">    <span class="comment">#选最近的点对</span></span><br><span class="line">    <span class="keyword">if</span>(right.dist&lt;best.dist):</span><br><span class="line">        best=right</span><br><span class="line">    merge(Y,<span class="string">&quot;y&quot;</span>,l,m,r)</span><br><span class="line"></span><br><span class="line">    k=l</span><br><span class="line">    <span class="comment">#距离中线最近的</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(l,r+<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">abs</span>(S[m].x-Y[i].x)&lt;best.dist):</span><br><span class="line">            Z[k]=Y[i]</span><br><span class="line">            k=k+<span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(l,k):</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(i+<span class="number">1</span>,k):</span><br><span class="line">            <span class="keyword">if</span>(Z[j].y-Z[i].y&lt;best.dist):</span><br><span class="line">                dp=dist(Z[i],Z[j])</span><br><span class="line">                <span class="keyword">if</span>(dp&lt;best.dist):</span><br><span class="line">                    best=Pair(S[Z[i].<span class="built_in">id</span>],S[Z[j].<span class="built_in">id</span>],dp)</span><br><span class="line">    <span class="comment">#返回最近点对</span></span><br><span class="line">    <span class="keyword">return</span> best</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">#一维点集</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">cpair1</span>(<span class="params">S</span>):</span></span><br><span class="line">    <span class="comment">#先设为正无穷</span></span><br><span class="line">    min_d=<span class="built_in">float</span>(<span class="string">&quot;inf&quot;</span>)</span><br><span class="line">    S=<span class="built_in">sorted</span>(S)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,<span class="built_in">len</span>(S)):</span><br><span class="line">        dist=<span class="built_in">abs</span>(S[i]-S[i-<span class="number">1</span>])</span><br><span class="line">        <span class="keyword">if</span>(dist&lt;min_d):</span><br><span class="line">            pair=[]</span><br><span class="line">            min_d=dist</span><br><span class="line">            pair.append([S[i-<span class="number">1</span>],S[i]])</span><br><span class="line">        <span class="keyword">elif</span>(dist==min_d):</span><br><span class="line">            pair.append([S[i-<span class="number">1</span>],S[i]])</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;Closest point:&quot;</span>)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> pair:</span><br><span class="line">        <span class="built_in">print</span>(i,end=<span class="string">&quot; &quot;</span>)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;\nMin_dist:&quot;</span>,min_d)</span><br><span class="line"></span><br><span class="line"><span class="comment">#二维点集</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">cpair2</span>(<span class="params">S</span>):</span></span><br><span class="line">    Y=[]</span><br><span class="line">    n=<span class="built_in">len</span>(S)</span><br><span class="line">    <span class="keyword">if</span>(n&lt;<span class="number">2</span>):</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="comment">#按X坐标排序</span></span><br><span class="line">    mergeSort(S,<span class="string">&quot;x&quot;</span>,<span class="number">0</span>,n-<span class="number">1</span>)</span><br><span class="line">    <span class="comment">#以Point2类型赋值</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        p=Point2(S[i].x,S[i].y,i)</span><br><span class="line">        Y.append(p)</span><br><span class="line">    <span class="comment">#按y坐标排序</span></span><br><span class="line">    mergeSort(Y,<span class="string">&quot;y&quot;</span>,<span class="number">0</span>,n-<span class="number">1</span>)</span><br><span class="line">    Z=Y[:]</span><br><span class="line">    <span class="keyword">return</span> closePair(S,Y,Z,<span class="number">0</span>,n-<span class="number">1</span>)</span><br><span class="line">    </span><br><span class="line">    </span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    <span class="comment">#输入一维还是二维点平面</span></span><br><span class="line">    model=<span class="built_in">input</span>(<span class="string">&quot;Please choose model of &#x27;1&#x27; or &#x27;2&#x27;:&quot;</span>).split()[<span class="number">0</span>]</span><br><span class="line">    S=[]</span><br><span class="line">    <span class="comment">#一维点对</span></span><br><span class="line">    <span class="keyword">if</span>(model == <span class="string">&#x27;1&#x27;</span>):</span><br><span class="line">        point=<span class="built_in">input</span>(<span class="string">&quot;Please input a group of number in order:\n&quot;</span>).split()</span><br><span class="line">        <span class="comment">#如果输入空点对</span></span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">len</span>(point)==<span class="number">0</span>):</span><br><span class="line">            <span class="keyword">raise</span> ValueError(<span class="string">&quot;您输入了空点对！&quot;</span>)</span><br><span class="line">        <span class="comment">#转换类型</span></span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(point)):</span><br><span class="line">            S.append(<span class="built_in">int</span>(point[i]))</span><br><span class="line">        <span class="comment">#输出最近点对</span></span><br><span class="line">        cpair1(S)</span><br><span class="line">    <span class="comment">#二维点对</span></span><br><span class="line">    <span class="keyword">elif</span>(model == <span class="string">&#x27;2&#x27;</span>):</span><br><span class="line">        <span class="comment">#输入点数</span></span><br><span class="line">        n=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input how many points:\n&quot;</span>))</span><br><span class="line">        <span class="keyword">if</span>(n==<span class="number">0</span>):</span><br><span class="line">            <span class="keyword">raise</span> ValueError(<span class="string">&quot;您输入了0个点！&quot;</span>)</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">            words=<span class="string">f&quot;please input the No.<span class="subst">&#123;i+<span class="number">1</span>&#125;</span> point (like: x y) in x order:&quot;</span></span><br><span class="line">            point=<span class="built_in">input</span>(words).split()</span><br><span class="line">            p=Point1(<span class="built_in">int</span>(point[<span class="number">0</span>]),<span class="built_in">int</span>(point[<span class="number">1</span>]),i)</span><br><span class="line">            S.append(p)</span><br><span class="line">        <span class="comment">#找到最近的一对点对</span></span><br><span class="line">        best=cpair2(S)</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">f&quot;The closest points are (<span class="subst">&#123;best.a.x&#125;</span>,<span class="subst">&#123;best.a.y&#125;</span>) and (<span class="subst">&#123;best.b.x&#125;</span>,<span class="subst">&#123;best.b.y&#125;</span>).&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">f&quot;And the distance is <span class="subst">&#123;best.dist**<span class="number">0.5</span>&#125;</span>.&quot;</span>)</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;没有这个选项！&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="comment">#异常处理</span></span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h1 id="第三章-动态规划"><a href="#第三章-动态规划" class="headerlink" title="第三章 动态规划"></a>第三章 动态规划</h1><ul><li>动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，但与分治法不同的是，适用于动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。</li><li>动态规划算法的步骤：<ul><li>①找出最优解的性质，并刻画其结构特征</li><li>②递归地定义最优值</li><li>③以自底向上的方式计算出最优值</li><li>④根据计算最优值时得到的信息，构造最优解</li></ul></li><li>动态规划算法的两个基本要素：<code>最优子结构</code>与<code>重叠子问题</code><ul><li>最优子结构性质：问题的最优解包含子问题的最优解</li><li>重叠子问题：在用递归算法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次</li><li>无后效性：一个问题被划分阶段后，阶段I中的状态只能由I+1中的状态通过状态转移方程得来，与其他状态没有关系，特别是与未发生的状态没有关系</li></ul></li><li>动态规划算法有一个变形方法——备忘录方法，这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每一个解过的子问题建立一个记录项（备忘录）以备需要时查看，也可以避免相同子问题的重复求解</li></ul><h2 id="3-1-矩阵连乘问题"><a href="#3-1-矩阵连乘问题" class="headerlink" title="3.1 矩阵连乘问题"></a>3.1 矩阵连乘问题</h2><ul><li><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MIK2dK.png" alt="MIK2dK.png"></li><li>m(i,j)是指从A[i]到A[j]（1≤i≤j≤n）的最少数乘次数</li><li>矩阵可乘条件：A的列数等于B的行数，若A是一个p×q矩阵，B是一个q×r矩阵，则AB总共需要pqr次数乘。</li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 矩阵连乘问题</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#计算最优值</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">matrixChain</span>(<span class="params">p,m,s</span>):</span></span><br><span class="line">    <span class="comment">#m[i][j]表示A[i]到A[j]所需的最少数乘次数</span></span><br><span class="line">    <span class="comment">#s[i][j]表示A[i]到A[j]所需的最少数乘法对应的分隔位置</span></span><br><span class="line">    n=<span class="built_in">len</span>(p)-<span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> r <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">2</span>,n+<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n-r+<span class="number">2</span>):</span><br><span class="line">            <span class="comment">#沿斜线方向递进</span></span><br><span class="line">            j=r+i-<span class="number">1</span></span><br><span class="line">            m[i][j]=m[i+<span class="number">1</span>][j]+p[i-<span class="number">1</span>]*p[i]*p[j]</span><br><span class="line">            s[i][j]=i</span><br><span class="line">            k=i+<span class="number">1</span></span><br><span class="line">            <span class="comment">#寻找i到j间最优分隔k</span></span><br><span class="line">            <span class="keyword">while</span>(k&lt;j):</span><br><span class="line">                t=m[i][k]+m[k+<span class="number">1</span>][j]+p[i-<span class="number">1</span>]*p[k]*p[j]</span><br><span class="line">                <span class="keyword">if</span>(t&lt;m[i][j]):</span><br><span class="line">                    m[i][j]=t</span><br><span class="line">                    s[i][j]=k</span><br><span class="line">                k=k+<span class="number">1</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#根据S递归输出</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">traceback</span>(<span class="params">s,i,j</span>):</span></span><br><span class="line">    <span class="keyword">if</span>(i==j):</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">f&quot;A[<span class="subst">&#123;i&#125;</span>]&quot;</span>,end=<span class="string">&quot;&quot;</span>)</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;(&quot;</span>,end=<span class="string">&quot;&quot;</span>)</span><br><span class="line">    traceback(s,i,s[i][j])</span><br><span class="line">    traceback(s,s[i][j]+<span class="number">1</span>,j)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;)&quot;</span>,end=<span class="string">&quot;&quot;</span>)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    p=[]</span><br><span class="line">    y=<span class="number">0</span></span><br><span class="line">    <span class="comment">#输入矩阵个数</span></span><br><span class="line">    n=<span class="built_in">input</span>(<span class="string">&quot;Please iuput the number of matrix:&quot;</span>).split()</span><br><span class="line">    <span class="comment">#异常处理</span></span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">len</span>(n)==<span class="number">0</span>):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;您输入了空矩阵！&quot;</span>)</span><br><span class="line">    n=<span class="built_in">int</span>(n[<span class="number">0</span>])</span><br><span class="line">    <span class="comment">#输入每个矩阵的信息</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        s=<span class="built_in">input</span>(<span class="string">f&quot;Input No.<span class="subst">&#123;i+<span class="number">1</span>&#125;</span> Matrix size,eg:5 5\n&quot;</span>).split()</span><br><span class="line">        <span class="comment">#判断是否能与前一项相乘</span></span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">len</span>(p)&gt;=<span class="number">1</span>):</span><br><span class="line">            <span class="keyword">if</span>(y!=<span class="built_in">int</span>(s[<span class="number">0</span>])):</span><br><span class="line">                <span class="keyword">raise</span> ValueError(<span class="string">&quot;您输入的矩阵不能相乘！&quot;</span>)</span><br><span class="line">        x,y=<span class="built_in">int</span>(s[<span class="number">0</span>]),<span class="built_in">int</span>(s[<span class="number">1</span>])</span><br><span class="line">        p.append(x)</span><br><span class="line">    p.append(y)</span><br><span class="line">    m=[]</span><br><span class="line">    s=[]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n+<span class="number">1</span>):</span><br><span class="line">        m.append([<span class="number">0</span>]*(n+<span class="number">1</span>))</span><br><span class="line">        s.append([<span class="number">0</span>]*(n+<span class="number">1</span>))</span><br><span class="line">    matrixChain(p,m,s)  </span><br><span class="line">    traceback(s,<span class="number">1</span>,n)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;\nCount times:&quot;</span>,m[<span class="number">1</span>][n])</span><br><span class="line">    </span><br><span class="line"></span><br><span class="line">    </span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ ==<span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="comment">#异常处理</span></span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h2 id="3-3-最长公共子序列"><a href="#3-3-最长公共子序列" class="headerlink" title="3.3 最长公共子序列"></a>3.3 最长公共子序列</h2><ul><li><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MI179S.png" alt="MI179S.png"><br>建立递归关系：</li><li><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MI399U.png" alt="MI399U.png"></li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 最长公共子序列问题</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">IcsLength</span>(<span class="params">x,y,b</span>):</span></span><br><span class="line">    m=<span class="built_in">len</span>(x)</span><br><span class="line">    n=<span class="built_in">len</span>(y)</span><br><span class="line">    <span class="comment">#初始化</span></span><br><span class="line">    c=[]</span><br><span class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(m+<span class="number">1</span>):</span><br><span class="line">        c.append([<span class="number">0</span>]*(n+<span class="number">1</span>))</span><br><span class="line">    <span class="comment">#逐个比较</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,m+<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>):</span><br><span class="line">            <span class="comment">#如果相等那么此时的最长公共长度为去除该位置的最长公共长度+1</span></span><br><span class="line">            <span class="keyword">if</span>(x[i-<span class="number">1</span>]==y[j-<span class="number">1</span>]):</span><br><span class="line">                c[i][j]=c[i-<span class="number">1</span>][j-<span class="number">1</span>]+<span class="number">1</span></span><br><span class="line">                <span class="comment">#记录c[i][j]的值是第一类子问题的解得到的</span></span><br><span class="line">                b[i][j]=<span class="number">1</span></span><br><span class="line">            <span class="comment">#如果对应位置不相等，则比较两个序列去掉这个不等值后哪边的最长子序列会更长</span></span><br><span class="line">            <span class="keyword">elif</span>(c[i-<span class="number">1</span>][j]&gt;=c[i][j-<span class="number">1</span>]):</span><br><span class="line">                c[i][j]=c[i-<span class="number">1</span>][j]</span><br><span class="line">                b[i][j]=<span class="number">2</span></span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                c[i][j]=c[i][j-<span class="number">1</span>]</span><br><span class="line">                b[i][j]=<span class="number">3</span></span><br><span class="line">    <span class="keyword">return</span> c[m][n]</span><br><span class="line"></span><br><span class="line"><span class="comment">#根据b[i][j]输出最长子序列</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">Ics</span>(<span class="params">i,j,x,b</span>):</span></span><br><span class="line">    <span class="keyword">if</span>(i==<span class="number">0</span> <span class="keyword">or</span> j==<span class="number">0</span>):</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="comment">#如果是第一类子问题的解，则说明该位置是公共部分</span></span><br><span class="line">    <span class="keyword">if</span>(b[i][j]==<span class="number">1</span>):</span><br><span class="line">        Ics(i-<span class="number">1</span>,j-<span class="number">1</span>,x,b)</span><br><span class="line">        <span class="built_in">print</span>(x[i-<span class="number">1</span>],end=<span class="string">&quot;&quot;</span>)</span><br><span class="line">    <span class="comment">#如果是第二类子问题的解，则说明此时Zk≠Xm</span></span><br><span class="line">    <span class="keyword">elif</span>(b[i][j]==<span class="number">2</span>):</span><br><span class="line">        Ics(i-<span class="number">1</span>,j,x,b)</span><br><span class="line">    <span class="comment">#Zk≠Yn</span></span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        Ics(i,j-<span class="number">1</span>,x,b)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    <span class="comment">#输入字符串</span></span><br><span class="line">    A=<span class="built_in">input</span>(<span class="string">&quot;Please input No.1 Ics:&quot;</span>).split()</span><br><span class="line">    B=<span class="built_in">input</span>(<span class="string">&quot;Please input No.2 Ics:&quot;</span>).split()</span><br><span class="line">    b=[]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(A)+<span class="number">1</span>):</span><br><span class="line">        b.append([<span class="number">0</span>]*(<span class="built_in">len</span>(B)+<span class="number">1</span>))</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;The longest length:&quot;</span>,IcsLength(A,B,b))</span><br><span class="line">    Ics(<span class="built_in">len</span>(A),<span class="built_in">len</span>(B),A,b)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__==<span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="comment">#异常处理</span></span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不会合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h2 id="3-4-凸多边形最优三角剖分"><a href="#3-4-凸多边形最优三角剖分" class="headerlink" title="3.4 凸多边形最优三角剖分"></a>3.4 凸多边形最优三角剖分</h2><ul><li>和矩阵连乘相似</li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 凸多边形最优三角剖分问题</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="keyword">from</span> isConvex <span class="keyword">import</span> isConvex</span><br><span class="line"></span><br><span class="line"><span class="comment">#计算最优值</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">minWeightTriangulation</span>(<span class="params">n,t,s,v</span>):</span></span><br><span class="line">    <span class="comment">#t[i][j]是凸子多边形vi-1,vi,...,vj的最优三角剖分对应的权函数值</span></span><br><span class="line">    <span class="keyword">for</span> r <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">2</span>,n+<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n-r+<span class="number">2</span>):</span><br><span class="line">            j=r+i-<span class="number">1</span></span><br><span class="line">            t[i][j]=t[i+<span class="number">1</span>][j]+weight(i-<span class="number">1</span>,i,j,v)</span><br><span class="line">            s[i][j]=i</span><br><span class="line">            k=i+<span class="number">1</span></span><br><span class="line">            <span class="comment">#遍历i到j的所有边</span></span><br><span class="line">            <span class="keyword">while</span>(k&lt;j):</span><br><span class="line">                u=t[i][k]+t[k+<span class="number">1</span>][j]+weight(i-<span class="number">1</span>,k,j,v)</span><br><span class="line">                <span class="keyword">if</span>(u&lt;t[i][j]):</span><br><span class="line">                    t[i][j]=u</span><br><span class="line">                    s[i][j]=k</span><br><span class="line">                k=k+<span class="number">1</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#根据s输出划分结果</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">traceback</span>(<span class="params">s,i,j</span>):</span></span><br><span class="line">    <span class="keyword">if</span>(i==j):</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">f&quot;B[<span class="subst">&#123;i&#125;</span>]&quot;</span>,end=<span class="string">&quot;&quot;</span>)</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;(&quot;</span>,end=<span class="string">&quot;&quot;</span>)</span><br><span class="line">    traceback(s,i,s[i][j])</span><br><span class="line">    traceback(s,s[i][j]+<span class="number">1</span>,j)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;)&quot;</span>,end=<span class="string">&quot;&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="comment">#根据距离计算权重</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">weight</span>(<span class="params">i,j,k,v</span>):</span></span><br><span class="line">    <span class="keyword">return</span> dist(i,j,v)+dist(i,k,v)+dist(k,j,v)</span><br><span class="line"></span><br><span class="line"><span class="comment">#计算距离</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">dist</span>(<span class="params">i,j,v</span>):</span></span><br><span class="line">    <span class="keyword">return</span> (v[i][<span class="number">0</span>]-v[j][<span class="number">0</span>])**<span class="number">2</span>+(v[i][<span class="number">1</span>]-v[j][<span class="number">1</span>])**<span class="number">2</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    v=[]</span><br><span class="line">    <span class="comment">#可选择手动输入和使用默认值</span></span><br><span class="line">    ans=<span class="built_in">input</span>(<span class="string">&quot;Do you want to use default v[]:(y / n )&quot;</span>)</span><br><span class="line">    <span class="keyword">if</span>(ans==<span class="string">&quot;y&quot;</span> <span class="keyword">or</span> ans==<span class="string">&quot;Y&quot;</span>):</span><br><span class="line">        v=[[<span class="number">6</span>,<span class="number">1</span>],[<span class="number">13</span>,<span class="number">1</span>],[<span class="number">16</span>,<span class="number">4</span>],[<span class="number">13</span>,<span class="number">7</span>],[<span class="number">6</span>,<span class="number">7</span>],[<span class="number">3</span>,<span class="number">4</span>]]</span><br><span class="line">        graph=<span class="string">&quot;&quot;&quot;-----@######@-------\n----#--------#------\n---#----------#-----\n--@------------@----\n---#----------#-----\n----#--------#------\n-----@######@-------\n&quot;&quot;&quot;</span></span><br><span class="line">        <span class="built_in">print</span>(graph)</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> v:</span><br><span class="line">            <span class="built_in">print</span>(<span class="string">f&quot;(<span class="subst">&#123;i[<span class="number">0</span>]&#125;</span>,<span class="subst">&#123;i[<span class="number">1</span>]&#125;</span>)&quot;</span>,end=<span class="string">&quot; &quot;</span>)</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">elif</span>(ans==<span class="string">&quot;n&quot;</span> <span class="keyword">or</span> ans==<span class="string">&quot;N&quot;</span>):</span><br><span class="line">        n=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the number of points:\n&quot;</span>))</span><br><span class="line">        <span class="keyword">if</span>(n==<span class="number">0</span>):</span><br><span class="line">            <span class="keyword">raise</span> ValueError(<span class="string">&quot;您输入了0！&quot;</span>)</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">            a=<span class="built_in">input</span>(<span class="string">f&quot;Input X and Y of No.<span class="subst">&#123;i+<span class="number">1</span>&#125;</span> point:(eg:X Y)\n&quot;</span>).split()</span><br><span class="line">            v.append([<span class="built_in">int</span>(a[<span class="number">0</span>]),<span class="built_in">int</span>(a[<span class="number">1</span>])])</span><br><span class="line">        </span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;对不起没有这个选项！&quot;</span>)</span><br><span class="line">    <span class="comment">#判断是不是图多边形</span></span><br><span class="line">    <span class="keyword">if</span>(<span class="keyword">not</span> isConvex(v)):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;您输入的不是凸多边形！请确认是否按顺序输入！&quot;</span>)</span><br><span class="line">    t=[]</span><br><span class="line">    s=[]</span><br><span class="line">    n=<span class="built_in">len</span>(v)</span><br><span class="line">    <span class="comment">#初始化</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        t.append([<span class="number">0</span>]*(n))</span><br><span class="line">        s.append([<span class="number">0</span>]*(n))</span><br><span class="line">    minWeightTriangulation(n-<span class="number">1</span>,t,s,v)</span><br><span class="line">    traceback(s,<span class="number">0</span>,n-<span class="number">1</span>)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__==<span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="comment">#异常处理</span></span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><p>判断是否为凸多边形</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">#判断是否为凸多边形</span></span><br><span class="line"><span class="string">&#x27;&#x27;&#x27;</span></span><br><span class="line"><span class="string">计算直线表达式</span></span><br><span class="line"><span class="string">param vertex1: 前一个顶点</span></span><br><span class="line"><span class="string">param vertex2: 后一个顶点</span></span><br><span class="line"><span class="string">return (type, param): 返回直线的类别及其描述参数</span></span><br><span class="line"><span class="string">&#x27;&#x27;&#x27;</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">kb</span>(<span class="params">vertex1, vertex2</span>):</span></span><br><span class="line">    x1 = vertex1[<span class="number">0</span>]</span><br><span class="line">    y1 = vertex1[<span class="number">1</span>]</span><br><span class="line">    x2 = vertex2[<span class="number">0</span>]</span><br><span class="line">    y2 = vertex2[<span class="number">1</span>]</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">if</span> x1==x2:</span><br><span class="line">        <span class="keyword">return</span> (<span class="number">0</span>, x1)      <span class="comment"># 0-垂直直线</span></span><br><span class="line">    <span class="keyword">if</span> y1==y2:              </span><br><span class="line">        <span class="keyword">return</span> (<span class="number">1</span>, y1)      <span class="comment"># 1-水平直线</span></span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        k = (y1-y2)/(x1-x2)</span><br><span class="line">        b = y1 - k*x1</span><br><span class="line">        <span class="keyword">return</span> (<span class="number">2</span>, k, b)    <span class="comment"># 2-倾斜直线</span></span><br><span class="line"></span><br><span class="line"><span class="string">&#x27;&#x27;&#x27;</span></span><br><span class="line"><span class="string">判断是否为凸多边形</span></span><br><span class="line"><span class="string">param vertexes: 构成多边形的所有顶点坐标列表，如[[0，0], [50, 0], [0, 50]]</span></span><br><span class="line"><span class="string">return convex: 布尔类型，为True说明该多边形为凸多边形，否则为凹多边形</span></span><br><span class="line"><span class="string">&#x27;&#x27;&#x27;</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">isConvex</span>(<span class="params">vertexes</span>):</span></span><br><span class="line">    <span class="comment"># 默认为凸多边形</span></span><br><span class="line">    convex = <span class="literal">True</span>   </span><br><span class="line">    </span><br><span class="line">    <span class="comment"># 多边形至少包含三个顶点</span></span><br><span class="line">    l = <span class="built_in">len</span>(vertexes)</span><br><span class="line">    <span class="keyword">if</span> l&lt;<span class="number">3</span>:</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;多边形至少包含三个顶点！&quot;</span>)</span><br><span class="line">    </span><br><span class="line">    <span class="comment"># 对每两个点组成的直线做判断</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(l):</span><br><span class="line">        pre = i</span><br><span class="line">        nex = (i+<span class="number">1</span>)%l</span><br><span class="line">        </span><br><span class="line">        <span class="comment"># 得到直线</span></span><br><span class="line">        line = kb(vertexes[pre], vertexes[nex])</span><br><span class="line">        </span><br><span class="line">        <span class="comment"># 计算所有点和直线的距离（可能为正也可能为负）</span></span><br><span class="line">        <span class="keyword">if</span> line[<span class="number">0</span>]==<span class="number">0</span>:</span><br><span class="line">            offset = [vertex[<span class="number">0</span>]-vertexes[pre][<span class="number">0</span>] <span class="keyword">for</span> vertex <span class="keyword">in</span> vertexes]</span><br><span class="line">        <span class="keyword">elif</span> line[<span class="number">0</span>]==<span class="number">1</span>:</span><br><span class="line">            offset = [vertex[<span class="number">1</span>]-vertexes[pre][<span class="number">1</span>] <span class="keyword">for</span> vertex <span class="keyword">in</span> vertexes]</span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            k, b = line[<span class="number">1</span>], line[<span class="number">2</span>]</span><br><span class="line">            offset = [k*vertex[<span class="number">0</span>]+b-vertex[<span class="number">1</span>] <span class="keyword">for</span> vertex <span class="keyword">in</span> vertexes]</span><br><span class="line">        </span><br><span class="line">        <span class="comment"># 计算两两距离的乘积，如果出现负数则存在两个点位于直线两侧，因此为凹多边形</span></span><br><span class="line">        <span class="keyword">for</span> o <span class="keyword">in</span> offset:</span><br><span class="line">            <span class="keyword">for</span> s <span class="keyword">in</span> offset:</span><br><span class="line">                <span class="keyword">if</span> o*s&lt;<span class="number">0</span>:</span><br><span class="line">                    convex = <span class="literal">False</span></span><br><span class="line">                    <span class="keyword">break</span></span><br><span class="line">            <span class="keyword">if</span> convex==<span class="literal">False</span>:</span><br><span class="line">                <span class="keyword">break</span></span><br><span class="line">                    </span><br><span class="line">        <span class="keyword">if</span> convex==<span class="literal">False</span>:</span><br><span class="line">            <span class="keyword">break</span></span><br><span class="line">            </span><br><span class="line">    <span class="comment"># 打印判断结果</span></span><br><span class="line">    <span class="keyword">if</span> convex==<span class="literal">True</span>:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;该多边形为凸多边形！&quot;</span>)</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;该多边形为凹多边形！&quot;</span>)</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">return</span> convex</span><br></pre></td></tr></table></figure><h2 id="3-9-0-1背包问题"><a href="#3-9-0-1背包问题" class="headerlink" title="3.9 0-1背包问题"></a>3.9 0-1背包问题</h2><ul><li><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MIGH1O.png" alt="MIGH1O.png"></li><li>其中m(i,j)是指背包容量为j，可选择物品为i，i+1，···，n时0-1背包问题的最优值</li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 0-1背包问题--动态规划</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#跳跃点法</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">knapsack_Pro</span>(<span class="params">n,v,w,C,p,x</span>):</span></span><br><span class="line">    <span class="comment">#head指向每一阶段跳跃点集合的开始</span></span><br><span class="line">    head=[<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n+<span class="number">1</span>)]</span><br><span class="line">    p[<span class="number">0</span>][<span class="number">0</span>],p[<span class="number">0</span>][<span class="number">1</span>]=<span class="number">0</span>,<span class="number">0</span></span><br><span class="line">    left,right,pnext,head[<span class="number">1</span>]=<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        k=left</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(left,right+<span class="number">1</span>):</span><br><span class="line">            <span class="keyword">if</span>(p[j][<span class="number">0</span>]+w[i]&gt;C):</span><br><span class="line">                <span class="keyword">break</span> </span><br><span class="line">            y=p[j][<span class="number">0</span>]+w[i]</span><br><span class="line">            m=p[j][<span class="number">1</span>]+v[i]</span><br><span class="line">            <span class="comment">#重量小于此数的跳跃点直接加进来，不会被支配</span></span><br><span class="line">            <span class="keyword">while</span>(k&lt;=right <span class="keyword">and</span> p[k][<span class="number">0</span>]&lt;y):</span><br><span class="line">                p[pnext][<span class="number">0</span>]=p[k][<span class="number">0</span>]</span><br><span class="line">                p[pnext][<span class="number">1</span>]=p[k][<span class="number">1</span>]</span><br><span class="line">                pnext+=<span class="number">1</span></span><br><span class="line">                k+=<span class="number">1</span></span><br><span class="line">            <span class="comment">#两个if判断新产生的点能否加入p</span></span><br><span class="line">            <span class="keyword">if</span>(k&lt;=right <span class="keyword">and</span> p[k][<span class="number">0</span>]==y):</span><br><span class="line">                <span class="keyword">if</span>(m&lt;p[k][<span class="number">1</span>]):</span><br><span class="line">                    m=p[k][<span class="number">1</span>]</span><br><span class="line">                k+=<span class="number">1</span></span><br><span class="line">            <span class="keyword">if</span>(m&gt;p[pnext-<span class="number">1</span>][<span class="number">1</span>]):</span><br><span class="line">                p[pnext][<span class="number">0</span>]=y</span><br><span class="line">                p[pnext][<span class="number">1</span>]=m</span><br><span class="line">                pnext+=<span class="number">1</span></span><br><span class="line">            <span class="comment">#取出可以支配的点</span></span><br><span class="line">            <span class="keyword">while</span>(k&lt;=right <span class="keyword">and</span> p[k][<span class="number">1</span>]&lt;=p[pnext-<span class="number">1</span>][<span class="number">1</span>]):</span><br><span class="line">                k+=<span class="number">1</span></span><br><span class="line"></span><br><span class="line">        <span class="comment">#上面break后</span></span><br><span class="line">        <span class="keyword">while</span>(k&lt;=right):</span><br><span class="line">            p[pnext][<span class="number">0</span>]=p[k][<span class="number">0</span>]</span><br><span class="line">            p[pnext][<span class="number">1</span>]=p[k][<span class="number">1</span>]</span><br><span class="line">            pnext+=<span class="number">1</span></span><br><span class="line">            k+=<span class="number">1</span></span><br><span class="line">        </span><br><span class="line">        left=right+<span class="number">1</span></span><br><span class="line">        right=pnext-<span class="number">1</span></span><br><span class="line">        head[i+<span class="number">1</span>]=pnext</span><br><span class="line">    traceback_Pro(n,w,v,p,head,x)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">traceback_Pro</span>(<span class="params">n,w,v,p,head,x</span>):</span></span><br><span class="line">    j=p[head[n]-<span class="number">1</span>][<span class="number">0</span>]</span><br><span class="line">    m=p[head[n]-<span class="number">1</span>][<span class="number">1</span>]</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;max value:&quot;</span>,m,<span class="string">&quot;max weight:&quot;</span>,j)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n)[::-<span class="number">1</span>]:</span><br><span class="line">        <span class="keyword">for</span> k <span class="keyword">in</span> <span class="built_in">range</span>(head[i],head[i+<span class="number">1</span>]-<span class="number">1</span>):</span><br><span class="line">            <span class="keyword">if</span>(p[k][<span class="number">0</span>]+w[i]==j <span class="keyword">and</span> p[k][<span class="number">1</span>]+v[i]==m):</span><br><span class="line">                x[i]=<span class="number">1</span></span><br><span class="line">                j=p[k][<span class="number">0</span>]</span><br><span class="line">                m=p[k][<span class="number">1</span>]</span><br><span class="line">                <span class="keyword">break</span></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">knapsack</span>(<span class="params">v,w,C,m</span>):</span></span><br><span class="line">    <span class="comment">#m[i][j]指背包容量为j，可选择物品为i，i+1，...，n时的0-1背包问题的最优值</span></span><br><span class="line">    n=<span class="built_in">len</span>(v)-<span class="number">1</span></span><br><span class="line">    <span class="comment">#只剩一个物品的情况</span></span><br><span class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(C):</span><br><span class="line">        m[n][j] = v[n] <span class="keyword">if</span> j&gt;=<span class="built_in">min</span>(w[n]-<span class="number">1</span>,C) <span class="keyword">else</span> <span class="number">0</span></span><br><span class="line">    <span class="comment">#普通情况</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n)[::-<span class="number">1</span>]:</span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(C):</span><br><span class="line">            m[i][j] = <span class="built_in">max</span>(m[i+<span class="number">1</span>][j],m[i+<span class="number">1</span>][j-w[i]]+v[i]) <span class="keyword">if</span> j&gt;w[i]-<span class="number">1</span> <span class="keyword">else</span> m[i+<span class="number">1</span>][j]</span><br><span class="line">    <span class="comment">#第一件物品</span></span><br><span class="line">    <span class="keyword">if</span>(n&gt;<span class="number">0</span>):</span><br><span class="line">        m[<span class="number">0</span>][C-<span class="number">1</span>]=m[<span class="number">1</span>][C-<span class="number">1</span>]</span><br><span class="line">        <span class="keyword">if</span> C-<span class="number">1</span>&gt;=w[<span class="number">0</span>]:</span><br><span class="line">            m[<span class="number">0</span>][C-<span class="number">1</span>]=<span class="built_in">max</span>(m[<span class="number">0</span>][C-<span class="number">1</span>],m[<span class="number">1</span>][C-<span class="number">1</span>-w[<span class="number">0</span>]]+v[<span class="number">0</span>])</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">traceback</span>(<span class="params">m,w,C,x</span>):</span></span><br><span class="line">    c=C-<span class="number">1</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(w)-<span class="number">1</span>):</span><br><span class="line">        <span class="comment">#没选物品i则x[i]=0</span></span><br><span class="line">        <span class="keyword">if</span> (m[i][c]==m[i+<span class="number">1</span>][c]):</span><br><span class="line">            x[i]=<span class="number">0</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            x[i]=<span class="number">1</span></span><br><span class="line">            c -= w[i]</span><br><span class="line">    <span class="comment">#对于最后一个物品</span></span><br><span class="line">    x[<span class="built_in">len</span>(w)-<span class="number">1</span>]=<span class="number">1</span> <span class="keyword">if</span> m[<span class="built_in">len</span>(w)-<span class="number">1</span>][c]&gt;<span class="number">0</span> <span class="keyword">else</span> <span class="number">0</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#输出格式</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">cout</span>(<span class="params">x,v,w</span>):</span></span><br><span class="line">    total_v=<span class="number">0</span></span><br><span class="line">    total_w=<span class="number">0</span></span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;Choose:&quot;</span>)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(v)):</span><br><span class="line">        <span class="keyword">if</span> x[i]==<span class="number">1</span>:</span><br><span class="line">            <span class="built_in">print</span>(<span class="string">f&quot;No.<span class="subst">&#123;i+<span class="number">1</span>&#125;</span> item: value is <span class="subst">&#123;v[i]&#125;</span> , weight is <span class="subst">&#123;w[i]&#125;</span>&quot;</span>)</span><br><span class="line">            total_v +=v[i]</span><br><span class="line">            total_w +=w[i]</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">f&quot;total value: <span class="subst">&#123;total_v&#125;</span>&quot;</span>)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">f&quot;total weight: <span class="subst">&#123;total_w&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    v=[]    <span class="comment">#物品的价值列表</span></span><br><span class="line">    w=[]    <span class="comment">#物品的重量列表</span></span><br><span class="line">    <span class="comment">#输入物品数量</span></span><br><span class="line">    n=<span class="built_in">input</span>(<span class="string">&quot;Please input the number of items:\n&quot;</span>)</span><br><span class="line">    <span class="keyword">if</span>(n==<span class="string">&quot;&quot;</span> <span class="keyword">or</span> n==<span class="string">&quot;0&quot;</span>):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;您输入了空值或0！&quot;</span>)</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        n=<span class="built_in">int</span>(n)</span><br><span class="line">    x=[<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n+<span class="number">1</span>)]</span><br><span class="line">    <span class="comment">#选择两种算法（课本上的）</span></span><br><span class="line">    ans=<span class="built_in">input</span>(<span class="string">&quot;Choose Knapsack or Knapsack_Pro?(1 or 2)\n&quot;</span>).split()[<span class="number">0</span>]</span><br><span class="line">    <span class="keyword">if</span> ans==<span class="string">&#x27;1&#x27;</span>:</span><br><span class="line">        m=[]    <span class="comment">#m(i,j)指背包容量为j，可选择物品为i，i+1，...，n时的0-1背包问题的最优值</span></span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">            item=<span class="built_in">input</span>(<span class="string">f&quot;please input No.<span class="subst">&#123;i+<span class="number">1</span>&#125;</span> item&#x27;s value(v) and weight(w):(eg:v w)\n&quot;</span>).split()</span><br><span class="line">            v.append(<span class="built_in">int</span>(item[<span class="number">0</span>]))</span><br><span class="line">            w.append(<span class="built_in">int</span>(item[<span class="number">1</span>]))</span><br><span class="line">        C=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the max weight of bag:\n&quot;</span>))</span><br><span class="line">        <span class="keyword">if</span>(C&lt;=<span class="number">0</span>):</span><br><span class="line">            <span class="keyword">raise</span> ValueError(<span class="string">&quot;背包容量不能≤0&quot;</span>)</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">            m.append([<span class="number">0</span>]*C)</span><br><span class="line">        knapsack(v,w,C,m)</span><br><span class="line">        traceback(m,w,C,x)</span><br><span class="line">        cout(x,v,w)</span><br><span class="line">    <span class="keyword">elif</span> ans==<span class="string">&#x27;2&#x27;</span>:</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">            item=<span class="built_in">input</span>(<span class="string">f&quot;please input No.<span class="subst">&#123;i+<span class="number">1</span>&#125;</span> item&#x27;s value(v) and weight(w):(eg:v w)\n&quot;</span>).split()</span><br><span class="line">            v.append(<span class="built_in">float</span>(item[<span class="number">0</span>]))</span><br><span class="line">            w.append(<span class="built_in">float</span>(item[<span class="number">1</span>]))</span><br><span class="line">        <span class="comment">#初始化</span></span><br><span class="line">        p=[[<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">2</span>)]<span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(n*n)]</span><br><span class="line">        C=<span class="built_in">float</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the max weight of bag:\n&quot;</span>))</span><br><span class="line">        <span class="keyword">if</span>(C&lt;=<span class="number">0</span>):</span><br><span class="line">            <span class="keyword">raise</span> ValueError(<span class="string">&quot;背包容量不能小于等于0&quot;</span>)</span><br><span class="line">        <span class="keyword">if</span>(n==<span class="number">1</span>):</span><br><span class="line">            <span class="keyword">if</span>(w[<span class="number">0</span>]&lt;=C):</span><br><span class="line">                x[<span class="number">0</span>]=<span class="number">1</span></span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                x[<span class="number">0</span>]=<span class="number">0</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            knapsack_Pro(n,v,w,C,p,x)</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">            <span class="keyword">if</span>(x[i]==<span class="number">1</span>):</span><br><span class="line">                <span class="built_in">print</span>(<span class="string">&quot;choose: value:&quot;</span>,v[i],<span class="string">&quot;weight:&quot;</span>,w[i])</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">f&quot;您输入了<span class="subst">&#123;ans&#125;</span>没有该选项！&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__==<span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="comment">#异常处理</span></span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h2 id="3-10-最优二叉搜索树"><a href="#3-10-最优二叉搜索树" class="headerlink" title="3.10 最优二叉搜索树"></a>3.10 最优二叉搜索树</h2><ul><li>二叉搜索树：存储于每个结点中的元素x大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素</li></ul><h1 id="第四章-贪心算法"><a href="#第四章-贪心算法" class="headerlink" title="第四章 贪心算法"></a>第四章 贪心算法</h1><ul><li>贪心算法：总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑它所作出的选择只是在某种意义上的局部最优选择。</li><li>使用贪心算法需满足：<ul><li>贪心选择性：指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到</li><li>最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质</li></ul></li><li>贪心算法适合的问题：有n个输入，其解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然可行解一般来说是不唯一的。那些使目标函数取极值的可行解，成为最优解。</li><li>贪心算法是一种分级处理方法，它首先根据题意，选取一种度量标准，然后按这种度量标准对这n个的输入排序，并按序依次输入，如果不满足条件，则不把此输入加到解当中。</li><li>贪心算法设计求解的核心问题：选择能产生问题最优解的最优量度标准。</li><li>贪心算法正确性的证明：<ul><li>①证明算法所求的问题具有优化子结构</li><li>②证明算法所求解的问题具有贪心选择性</li><li>③算法按照②种的贪心选择性进行局部最优选择</li></ul></li></ul><h2 id="4-2-活动安排问题"><a href="#4-2-活动安排问题" class="headerlink" title="4.2 活动安排问题"></a>4.2 活动安排问题</h2><ul><li>为了选择最多的相容活动，每次选择fi最小的活动，使能够选择更多的活动</li><li>度量标准：按照结束时间的非减序排列</li><li>如果有序，则O(n)，如果无序，O(nlogn)</li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 活动安排问题</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#活动类，每个活动包括开始时间和结束时间</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">activity</span>():</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,ss,ff</span>):</span></span><br><span class="line">        self.s=ss</span><br><span class="line">        self.f=ff</span><br><span class="line">    </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">greedySelector</span>(<span class="params">arr,a</span>):</span></span><br><span class="line">    n=<span class="built_in">len</span>(arr)-<span class="number">1</span></span><br><span class="line">    a[<span class="number">0</span>]=<span class="literal">True</span></span><br><span class="line">    j=<span class="number">0</span></span><br><span class="line">    count=<span class="number">1</span></span><br><span class="line">    <span class="comment">#满足开始时间大于上一个活动的结束时间的加入（设为True）</span></span><br><span class="line">    <span class="comment">#O(n)</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">if</span>(arr[i].s&gt;=arr[j].f):</span><br><span class="line">            a[i]=<span class="literal">True</span></span><br><span class="line">            j=i</span><br><span class="line">            count+=<span class="number">1</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            a[i]=<span class="literal">False</span></span><br><span class="line">    <span class="keyword">return</span> count</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    activities=[]</span><br><span class="line">    <span class="comment">#输入数据</span></span><br><span class="line">    n=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;please input the number of activities:\n&quot;</span>))</span><br><span class="line">    <span class="comment">#异常处理</span></span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">0</span>):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;您输入了0！&quot;</span>)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;Use greedy selector , activities should be ordered by the end_time.&quot;</span>)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        item=<span class="built_in">input</span>(<span class="string">&quot;please input the begin-time and end-time:(eg: 3 6)\n&quot;</span>).split()</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">len</span>(item)!=<span class="number">2</span>):</span><br><span class="line">            <span class="keyword">raise</span> ValueError(<span class="string">&quot;您输入的数据个数不合法！&quot;</span>)</span><br><span class="line">        s=activity(<span class="built_in">float</span>(item[<span class="number">0</span>]),<span class="built_in">float</span>(item[<span class="number">1</span>])) </span><br><span class="line">        activities.append(s)</span><br><span class="line">    <span class="comment">#以结束时间非减序排序</span></span><br><span class="line">    activities=<span class="built_in">sorted</span>(activities,key=<span class="keyword">lambda</span> x:x.f)</span><br><span class="line">    <span class="comment">#初始化选择集合a</span></span><br><span class="line">    a=[<span class="literal">False</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n)]</span><br><span class="line">    count=greedySelector(activities,a)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;Maximum number of activities:&quot;</span>,count)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;Choose:&quot;</span>,a)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h2 id="4-3-最优装载问题"><a href="#4-3-最优装载问题" class="headerlink" title="4.3 最优装载问题"></a>4.3 最优装载问题</h2><ul><li>O(nlogn)</li></ul><h2 id="4-4-哈夫曼编码"><a href="#4-4-哈夫曼编码" class="headerlink" title="4.4 哈夫曼编码"></a>4.4 哈夫曼编码</h2><ul><li>循环地选择具有最低频率的两个结点，生成一棵子树，直至形成树</li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">#构建二叉树类型</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BinaryTree</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,data,left,right,code</span>):</span></span><br><span class="line">        self.data=data</span><br><span class="line">        self.left=left</span><br><span class="line">        self.right=right</span><br><span class="line">        self.code=code</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">getdata</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="keyword">return</span> self.data</span><br><span class="line"></span><br><span class="line"><span class="comment">#哈夫曼树</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Huffman</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,tree,ww</span>):</span></span><br><span class="line">        self.tree=tree</span><br><span class="line">        self.w=ww</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">getweight</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="keyword">return</span> self.w</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">huffmanTree</span>(<span class="params">f</span>):</span></span><br><span class="line">    <span class="comment">#f是出现频率权值字典</span></span><br><span class="line">    H=[]</span><br><span class="line">    n=<span class="built_in">len</span>(f)</span><br><span class="line">    <span class="comment">#根据value对键进行从大到小排序</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">sorted</span>(f,key=f.__getitem__,reverse=<span class="literal">True</span>):</span><br><span class="line">        tree = BinaryTree(i,<span class="number">0</span>,<span class="number">0</span>,<span class="string">&quot;&quot;</span>)</span><br><span class="line">        w = Huffman(tree,f[i])</span><br><span class="line">        H.append(w)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n):</span><br><span class="line">        <span class="comment">#取出最后两位</span></span><br><span class="line">        x=H.pop()</span><br><span class="line">        y=H.pop()</span><br><span class="line">        <span class="comment">#取权重小的做左孩子，大的是右孩子</span></span><br><span class="line">        t=BinaryTree(i,x.tree <span class="keyword">if</span> x.w&lt;y.w <span class="keyword">else</span> y.tree,y.tree <span class="keyword">if</span> y.w&gt;x.w <span class="keyword">else</span> x.tree,<span class="string">&quot;&quot;</span>)</span><br><span class="line">        h=Huffman(t,x.w+y.w)</span><br><span class="line">        H.append(h)</span><br><span class="line">        <span class="comment">#根据权重从大到小排序</span></span><br><span class="line">        H=<span class="built_in">sorted</span>(H,key=<span class="keyword">lambda</span> x:x.w,reverse=<span class="literal">True</span>)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> H.pop()</span><br></pre></td></tr></table></figure><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile </span></span><br><span class="line"><span class="string">Title: 哈夫曼编码</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="comment">#构建二叉树类型</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BinaryTree</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,data,left,right,code</span>):</span></span><br><span class="line">        self.data=data</span><br><span class="line">        self.left=left</span><br><span class="line">        self.right=right</span><br><span class="line">        self.code=code</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">getdata</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="keyword">return</span> self.data</span><br><span class="line"></span><br><span class="line"><span class="comment">#哈夫曼树</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Huffman</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,tree,ww</span>):</span></span><br><span class="line">        self.tree=tree</span><br><span class="line">        self.w=ww</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">getweight</span>(<span class="params">self</span>):</span></span><br><span class="line">        <span class="keyword">return</span> self.w</span><br><span class="line">    </span><br><span class="line"><span class="comment">#计算权重</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">makedict</span>(<span class="params">s</span>):</span></span><br><span class="line">    dic=&#123;&#125;</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> s:</span><br><span class="line">        <span class="keyword">if</span> i <span class="keyword">not</span> <span class="keyword">in</span> dic.keys():</span><br><span class="line">            dic[i]=<span class="number">1</span></span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            dic[i]+=<span class="number">1</span></span><br><span class="line">    <span class="keyword">return</span> dic</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">huffmanTree</span>(<span class="params">f</span>):</span></span><br><span class="line">    <span class="comment">#f是出现频率权值字典</span></span><br><span class="line">    H=[]</span><br><span class="line">    n=<span class="built_in">len</span>(f)</span><br><span class="line">    <span class="comment">#根据value对键进行从大到小排序</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">sorted</span>(f,key=f.__getitem__,reverse=<span class="literal">True</span>):</span><br><span class="line">        tree = BinaryTree(i,<span class="number">0</span>,<span class="number">0</span>,<span class="string">&quot;&quot;</span>)</span><br><span class="line">        w = Huffman(tree,f[i])</span><br><span class="line">        H.append(w)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n):</span><br><span class="line">        <span class="comment">#取出最后两位</span></span><br><span class="line">        x=H.pop()</span><br><span class="line">        y=H.pop()</span><br><span class="line">        <span class="comment">#取权重小的做左孩子，大的是右孩子</span></span><br><span class="line">        t=BinaryTree(i,x.tree <span class="keyword">if</span> x.w&lt;y.w <span class="keyword">else</span> y.tree,y.tree <span class="keyword">if</span> y.w&gt;x.w <span class="keyword">else</span> x.tree,<span class="string">&quot;&quot;</span>)</span><br><span class="line">        h=Huffman(t,x.w+y.w)</span><br><span class="line">        H.append(h)</span><br><span class="line">        <span class="comment">#根据权重从大到小排序</span></span><br><span class="line">        H=<span class="built_in">sorted</span>(H,key=<span class="keyword">lambda</span> x:x.w,reverse=<span class="literal">True</span>)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> H.pop()</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">listall</span>(<span class="params">h</span>):</span></span><br><span class="line">    m=[]</span><br><span class="line">    k=[]</span><br><span class="line">    left,right=h.tree.left,h.tree.right</span><br><span class="line">    rcode=<span class="string">&quot;1&quot;</span></span><br><span class="line">    lcode=<span class="string">&quot;0&quot;</span></span><br><span class="line">    m.append(right)</span><br><span class="line">    right.code+=rcode</span><br><span class="line">    m.append(left)</span><br><span class="line">    left.code+=lcode</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">len</span>(m)&gt;<span class="number">0</span>):</span><br><span class="line">        <span class="comment">#如果存在左孩子（左右必同时存在）</span></span><br><span class="line">        <span class="keyword">if</span>(m[-<span class="number">1</span>].left):</span><br><span class="line">            a=m.pop()</span><br><span class="line">            c=a.code</span><br><span class="line">            m.append(a.right)</span><br><span class="line">            a.right.code=c+rcode</span><br><span class="line">            m.append(a.left)</span><br><span class="line">            a.left.code=c+lcode</span><br><span class="line">        <span class="keyword">else</span>:</span><br><span class="line">            b=m.pop()</span><br><span class="line">            k.append(b)</span><br><span class="line">    <span class="keyword">return</span> k</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">back</span>(<span class="params">hfmcode,filename</span>):</span></span><br><span class="line">    ans=<span class="built_in">input</span>(<span class="string">f&quot;Do you want to decode &#x27;<span class="subst">&#123;filename&#125;</span>&#x27;?（y/n）\n&quot;</span>)</span><br><span class="line">    <span class="keyword">if</span>(ans!=<span class="string">&quot;y&quot;</span> <span class="keyword">and</span> ans!=<span class="string">&#x27;Y&#x27;</span>):</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="comment">#读取要解压缩的文件</span></span><br><span class="line">    <span class="keyword">with</span> <span class="built_in">open</span>(filename,<span class="string">&#x27;r&#x27;</span>) <span class="keyword">as</span> f:</span><br><span class="line">        s=f.read()</span><br><span class="line">    st=<span class="string">&quot;&quot;</span></span><br><span class="line">    <span class="comment">#键和值交换形成新字典</span></span><br><span class="line">    new_dict = &#123;v:k <span class="keyword">for</span> k,v <span class="keyword">in</span> hfmcode.items()&#125;</span><br><span class="line">    <span class="comment">#写入新文件</span></span><br><span class="line">    <span class="keyword">with</span> <span class="built_in">open</span>(<span class="string">&#x27;解压缩.txt&#x27;</span>,<span class="string">&#x27;w&#x27;</span>) <span class="keyword">as</span> f:</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> s:</span><br><span class="line">            st+=i</span><br><span class="line">            <span class="keyword">if</span>(st <span class="keyword">in</span> hfmcode.values()):</span><br><span class="line">                f.write(new_dict[st])</span><br><span class="line">                st=<span class="string">&quot;&quot;</span></span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;==&quot;</span>*<span class="number">10</span>)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;ok!Please check the file: &#x27;解压缩.txt&#x27;&quot;</span>)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;==&quot;</span>*<span class="number">10</span>)</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    filename1=<span class="string">&quot;测试用例.txt&quot;</span></span><br><span class="line">    filename2=<span class="string">&#x27;编码后.txt&#x27;</span></span><br><span class="line">    <span class="comment">#可以选择读文件和输入字符串</span></span><br><span class="line">    s=<span class="built_in">input</span>(<span class="string">f&quot;Do you want to search <span class="subst">&#123;filename1&#125;</span>！（y/n）\n&quot;</span>)</span><br><span class="line">    <span class="keyword">if</span>(s==<span class="string">&quot;y&quot;</span> <span class="keyword">or</span> s==<span class="string">&quot;Y&quot;</span>):</span><br><span class="line">        <span class="comment">#读文件</span></span><br><span class="line">        <span class="keyword">with</span> <span class="built_in">open</span>(filename1,<span class="string">&#x27;r&#x27;</span>) <span class="keyword">as</span> f:</span><br><span class="line">            s=f.read()</span><br><span class="line">        <span class="comment">#权值字典</span></span><br><span class="line">        dic=makedict(s)</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;权值：&quot;</span>,dic)</span><br><span class="line">        <span class="comment">#构建哈夫曼树</span></span><br><span class="line">        hTree=huffmanTree(dic)</span><br><span class="line">        <span class="comment">#编码</span></span><br><span class="line">        k=listall(hTree)</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;哈夫曼编码：&quot;</span>)</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> k:</span><br><span class="line">            <span class="built_in">print</span>(i.data,i.code)</span><br><span class="line">        <span class="comment">#存储值对应的编码</span></span><br><span class="line">        hfmcode=&#123;&#125;</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> k:</span><br><span class="line">            hfmcode[i.data]=i.code</span><br><span class="line">        <span class="comment">#写入哈夫曼编码</span></span><br><span class="line">        <span class="keyword">with</span> <span class="built_in">open</span>(filename2,<span class="string">&#x27;w&#x27;</span>) <span class="keyword">as</span> f:</span><br><span class="line">            <span class="keyword">for</span> i <span class="keyword">in</span> s:</span><br><span class="line">                string=hfmcode[i]</span><br><span class="line">                f.write(string)</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;==&quot;</span>*<span class="number">10</span>)</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">f&quot;ok!Please check the file: &#x27;<span class="subst">&#123;filename2&#125;</span>&#x27;&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;==&quot;</span>*<span class="number">10</span>)</span><br><span class="line">        back(hfmcode,filename2)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        s=<span class="built_in">input</span>(<span class="string">&quot;Please input the string:&quot;</span>)</span><br><span class="line">        dic=makedict(s)</span><br><span class="line">        <span class="built_in">print</span>(dic)</span><br><span class="line">        hTree=huffmanTree(dic)</span><br><span class="line">        k=listall(hTree)</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> k:</span><br><span class="line">            <span class="built_in">print</span>(i.data,i.code)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h2 id="4-5-单源最短路径"><a href="#4-5-单源最短路径" class="headerlink" title="4.5 单源最短路径"></a>4.5 单源最短路径</h2><ul><li>设置顶点集合S并不断地作贪心选择来扩充这个集合，一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知，初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路径长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度</li></ul><h2 id="4-6-最小生成树"><a href="#4-6-最小生成树" class="headerlink" title="4.6 最小生成树"></a>4.6 最小生成树</h2><ul><li>设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为<code>c[v][w]</code>。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树</li><li>最小生成树性质（MST性质）：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)∈E，且u∈U，v∈V-U，且在所有这样的边中，(u,v)的权为<code>c[u][v]</code>最小，那么一定存在G的一颗最小生成树，它以(u,v)为其中一条边</li><li>Prim算法：<ul><li>首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：</li><li>选取满足条件i∈S，j∈V-S，且<code>c[i][j]</code>最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。</li><li>在这个过程中选取到的所有边恰好构成G的一棵最小生成树。<br><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MIjycj.png" alt="MIjycj.png"></li></ul></li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 最小生成树-Prim算法</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">prim</span>(<span class="params">n,c</span>):</span></span><br><span class="line">    <span class="comment">#初始化Prim算法的数组</span></span><br><span class="line">    s=[<span class="number">1</span>]</span><br><span class="line">    p=[<span class="number">1</span>]</span><br><span class="line">    lowcost=[<span class="built_in">float</span>(<span class="string">&#x27;inf&#x27;</span>) <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n)]</span><br><span class="line">    m=<span class="number">1</span></span><br><span class="line">    <span class="comment">#遍历S中的点</span></span><br><span class="line">    <span class="keyword">for</span> r <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n):</span><br><span class="line">        ns=<span class="built_in">len</span>(s)</span><br><span class="line">        <span class="keyword">for</span> t <span class="keyword">in</span> <span class="built_in">range</span>(ns):</span><br><span class="line">            i=s[t]</span><br><span class="line">            <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>):</span><br><span class="line">                <span class="comment">#如果不在S中，且最短则记录</span></span><br><span class="line">                <span class="keyword">if</span>(j <span class="keyword">not</span> <span class="keyword">in</span> s) <span class="keyword">and</span> (c[i][j]&lt;lowcost[m]):</span><br><span class="line">                    lowcost[m]=c[i][j]</span><br><span class="line">                    k=j</span><br><span class="line">                    u=i</span><br><span class="line">        m+=<span class="number">1</span></span><br><span class="line">        s.append(k)</span><br><span class="line">        p.append(u)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,<span class="built_in">len</span>(s)):</span><br><span class="line">        <span class="built_in">print</span>(s[i],p[i],c[s[i]][p[i]])</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    <span class="comment">#输入点数</span></span><br><span class="line">    n=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the number of points:\n&quot;</span>))</span><br><span class="line">    <span class="comment">#初始化边长</span></span><br><span class="line">    c=[[<span class="built_in">float</span>(<span class="string">&#x27;inf&#x27;</span>) <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n+<span class="number">1</span>)] <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(n+<span class="number">1</span>)]</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>):</span><br><span class="line">        c[i][i]=<span class="number">0</span></span><br><span class="line">    <span class="keyword">if</span>(n&lt;=<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">f&quot;You input <span class="subst">&#123;n&#125;</span> point.&quot;</span>)</span><br><span class="line">    <span class="comment">#输入边长</span></span><br><span class="line">    g=<span class="built_in">input</span>(<span class="string">&quot;Please input the p1,p2 and weight,like: 1 2 4\nInput end to end.\n&quot;</span>)</span><br><span class="line">    <span class="keyword">while</span>(g!=<span class="string">&#x27;end&#x27;</span>):</span><br><span class="line">        a=g.split()</span><br><span class="line">        i=<span class="built_in">int</span>(a[<span class="number">0</span>])</span><br><span class="line">        j=<span class="built_in">int</span>(a[<span class="number">1</span>])</span><br><span class="line">        w=<span class="built_in">float</span>(a[<span class="number">2</span>])</span><br><span class="line">        c[i][j]=w</span><br><span class="line">        c[j][i]=w</span><br><span class="line">        g=<span class="built_in">input</span>(<span class="string">&quot;Please input the p1,p2 and weight,like: 1 2 4\nInput end to end.\n&quot;</span>)</span><br><span class="line">    </span><br><span class="line">    prim(n,c)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__==<span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><ul><li>Kruskal算法：<ul><li>首先，将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。</li><li>然后，从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：<ul><li>当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；</li><li>如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。</li><li>这个过程一直进行到只剩下一个连通分支时为止。<br><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MIvIdP.png" alt="MIvIdP.png"></li></ul></li></ul></li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 最小生成树-Kruskal算法</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Edge</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,u,v,w</span>):</span></span><br><span class="line">        self.u=u</span><br><span class="line">        self.v=v</span><br><span class="line">        self.w=w</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">EdgeNode</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,p,g</span>):</span></span><br><span class="line">        self.<span class="built_in">id</span>=p</span><br><span class="line">        self.g=g</span><br><span class="line">    </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">kruskal</span>(<span class="params">n,e</span>):</span></span><br><span class="line">    e=<span class="built_in">sorted</span>(e,key=<span class="keyword">lambda</span> x: x.w)</span><br><span class="line">    en=<span class="built_in">len</span>(e)</span><br><span class="line">    s=[<span class="number">0</span>]</span><br><span class="line">    e[<span class="number">0</span>].u.g,e[<span class="number">0</span>].v.g=<span class="number">0</span>,<span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(en):</span><br><span class="line">        <span class="keyword">if</span>(j <span class="keyword">not</span> <span class="keyword">in</span> s) <span class="keyword">and</span> (e[j].u.g!=e[j].v.g):</span><br><span class="line">            m=e[j].u.g <span class="keyword">if</span> e[j].u.g&lt;e[j].v.g <span class="keyword">else</span> e[j].v.g</span><br><span class="line">            <span class="keyword">for</span> eachedge <span class="keyword">in</span> e:</span><br><span class="line">                <span class="keyword">if</span> (eachedge.u==e[j].u <span class="keyword">or</span> eachedge.v==e[j].v <span class="keyword">or</span> eachedge.u==e[j].v <span class="keyword">or</span> eachedge.v==e[j].u) <span class="keyword">and</span> (eachedge.u.g==eachedge.v.g):</span><br><span class="line">                    m=<span class="built_in">min</span>(eachedge.u.g,eachedge.v.g,m)</span><br><span class="line">                    eachedge.u.g=eachedge.v.g=m</span><br><span class="line">            e[j].u.g=e[j].v.g=m</span><br><span class="line">            s.append(j)</span><br><span class="line">    </span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(s)):</span><br><span class="line">        <span class="built_in">print</span>(e[s[i]].u.<span class="built_in">id</span>,e[s[i]].v.<span class="built_in">id</span>,e[s[i]].w)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    <span class="comment">#输入点数</span></span><br><span class="line">    n=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the number of points:\n&quot;</span>))</span><br><span class="line">    <span class="keyword">if</span>(n&lt;=<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">f&quot;You input <span class="subst">&#123;n&#125;</span> point.&quot;</span>)</span><br><span class="line">    <span class="comment">#输入边长</span></span><br><span class="line">    e=[]</span><br><span class="line">    p=&#123;&#125;</span><br><span class="line">    g=<span class="built_in">input</span>(<span class="string">&quot;Please input the p1,p2 and weight,like: 1 2 4\nInput end to end.\n&quot;</span>)</span><br><span class="line">    aa,bb=n,n+<span class="number">1</span></span><br><span class="line">    <span class="keyword">while</span>(g!=<span class="string">&#x27;end&#x27;</span>):</span><br><span class="line">        a=g.split()</span><br><span class="line">        i,j,w=<span class="built_in">int</span>(a[<span class="number">0</span>]),<span class="built_in">int</span>(a[<span class="number">1</span>]),<span class="built_in">float</span>(a[<span class="number">2</span>])</span><br><span class="line">        <span class="keyword">if</span>(i <span class="keyword">not</span> <span class="keyword">in</span> p.keys()):</span><br><span class="line">            p[i]=EdgeNode(i,aa)</span><br><span class="line">        <span class="keyword">if</span>(j <span class="keyword">not</span> <span class="keyword">in</span> p.keys()):</span><br><span class="line">            p[j]=EdgeNode(j,bb)</span><br><span class="line">        e.append(Edge(p[i],p[j],w))</span><br><span class="line">        g=<span class="built_in">input</span>(<span class="string">&quot;Please input the p1,p2 and weight,like: 1 2 4\nInput end to end.\n&quot;</span>)</span><br><span class="line">        aa+=<span class="number">1</span></span><br><span class="line">        bb+=<span class="number">1</span></span><br><span class="line"></span><br><span class="line">    kruskal(n,e)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__==<span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h1 id="第五章-回溯法"><a href="#第五章-回溯法" class="headerlink" title="第五章 回溯法"></a>第五章 回溯法</h1><ul><li><p>回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该节点为根的子树的搜索，逐层向其祖先结点回溯，否则，进入该子树，继续按深度优先策略搜索</p></li><li><p>具有剪枝函数的深度优先生成法</p></li><li><p>扩展结点：正在产生儿子的结点称为扩展结点</p></li><li><p>活结点：自身已生成但其儿子还没有全部生成的结点</p></li><li><p>回溯法的步骤：</p><ul><li>(1)针对所给问题，定义问题的解空间；</li><li>(2)确定易于搜索的解空间结构；</li><li>(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索</li></ul></li><li><p>子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。通常有2n个叶子节点，其节点总个数为2n+1-1。如：0-1背包问题</p></li><li><p>排列树：当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n！个叶子节点。如：旅行售货员问题。</p></li><li><p>回溯算法的效率在很大程度上依赖于以下因素：</p><ul><li>(1)产生x[k]的时间；</li><li>(2)满足显约束的x[k]值的个数；</li><li>(3)计算约束函数constraint的时间；</li><li>(4)计算上界函数bound的时间；</li><li>(5)满足约束函数和上界函数约束的所有x[k]的个数。好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。</li></ul></li></ul><h2 id="5-2-装载问题"><a href="#5-2-装载问题" class="headerlink" title="5.2 装载问题"></a>5.2 装载问题</h2><ul><li>如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。<ul><li>(1)首先将第一艘轮船尽可能装满；</li><li>(2)将剩余的集装箱装上第二艘轮船。</li></ul></li><li>解空间：子集树</li><li>可行性约束函数(选择当前元素)：</li><li>上界函数(不选择当前元素)：当前载重量cw+剩余集装箱的重量r≤当前最优载重量bestw</li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 装载问题（回溯法）</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">backtrack</span>(<span class="params">i,c</span>):</span></span><br><span class="line">    <span class="keyword">global</span> w,bestx,x,bestw,r,cw</span><br><span class="line">    <span class="keyword">if</span>(i&gt;<span class="built_in">len</span>(w)-<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">if</span>(cw&gt;bestw):</span><br><span class="line">            <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,<span class="built_in">len</span>(w)):</span><br><span class="line">                bestx[j]=x[j]</span><br><span class="line">            bestw=cw</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">#逐层搜索子树</span></span><br><span class="line">    r-=w[i]</span><br><span class="line">    <span class="keyword">if</span>(cw+w[i]&lt;=c):</span><br><span class="line">        x[i]=<span class="number">1</span></span><br><span class="line">        cw+=w[i]</span><br><span class="line">        backtrack(i+<span class="number">1</span>,c)</span><br><span class="line">        cw-=w[i]</span><br><span class="line">    <span class="keyword">if</span>(cw+r&gt;bestw):</span><br><span class="line">        x[i]=<span class="number">0</span></span><br><span class="line">        backtrack(i+<span class="number">1</span>,c)</span><br><span class="line">    r+=w[i]</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    <span class="keyword">global</span> w,bestx,x,bestw,r,cw</span><br><span class="line">    w=[<span class="number">0</span>]</span><br><span class="line">    m=<span class="built_in">input</span>(<span class="string">&quot;Please input the weight of each items:(eg:1 2 3 4 5)\n&quot;</span>).split()</span><br><span class="line">    n=<span class="built_in">len</span>(m)    <span class="comment">#物品数量</span></span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">0</span>):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;物品数量不能为空！&quot;</span>)</span><br><span class="line">    r=<span class="number">0</span>         <span class="comment">#剩余的物品容量</span></span><br><span class="line">    <span class="comment">#转换w类型并初始化r</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        w.append(<span class="built_in">int</span>(m[i]))</span><br><span class="line">        r+=w[i+<span class="number">1</span>]</span><br><span class="line">    c1=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the size of No.1 ship:\n&quot;</span>))      <span class="comment">#第一艘船载重量</span></span><br><span class="line">    c2=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the size of No.2 ship:\n&quot;</span>))      <span class="comment">#第二艘船载重量</span></span><br><span class="line"></span><br><span class="line">    x=[<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n+<span class="number">1</span>)]         <span class="comment">#记录路径</span></span><br><span class="line">    bestx=x[:]                      <span class="comment">#最优路径</span></span><br><span class="line">    bestw,cw=<span class="number">0</span>,<span class="number">0</span>                    <span class="comment">#最优载重量，当前载重量</span></span><br><span class="line">    <span class="comment">#尽可能的装满第一个</span></span><br><span class="line">    backtrack(<span class="number">1</span>,c1)</span><br><span class="line">    <span class="comment">#print(bestx)</span></span><br><span class="line">    cw2=<span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,<span class="built_in">len</span>(bestx)):</span><br><span class="line">        <span class="keyword">if</span>(bestx[i]==<span class="number">0</span>):</span><br><span class="line">            cw2+=w[i]</span><br><span class="line">    <span class="keyword">if</span>(cw2&gt;c2):</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;不能由两艘船装完！&quot;</span>)</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="keyword">else</span>:</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,<span class="built_in">len</span>(bestx)):</span><br><span class="line">            <span class="keyword">if</span>(bestx[i]==<span class="number">1</span>):</span><br><span class="line">                <span class="built_in">print</span>(<span class="string">f&quot;第<span class="subst">&#123;i&#125;</span>个物品，重量<span class="subst">&#123;w[i]&#125;</span>,装入第1艘船&quot;</span>)</span><br><span class="line">            <span class="keyword">else</span>:</span><br><span class="line">                <span class="built_in">print</span>(<span class="string">f&quot;第<span class="subst">&#123;i&#125;</span>个物品，重量<span class="subst">&#123;w[i]&#125;</span>,装入第2艘船&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h2 id="5-6-0-1背包问题"><a href="#5-6-0-1背包问题" class="headerlink" title="5.6 0-1背包问题"></a>5.6 0-1背包问题</h2><ul><li>n=3, C=30, w={16, 15, 15}, v={45, 25, 25}</li><li><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/Mo9ygU.png" alt="Mo9ygU.png"></li></ul><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 0-1背包问题（回溯法）</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Q</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,_id,qq</span>):</span></span><br><span class="line">        self.<span class="built_in">id</span>=_<span class="built_in">id</span></span><br><span class="line">        self.d=qq</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bound</span>(<span class="params">i</span>):</span></span><br><span class="line">    <span class="keyword">global</span> bestp,cw,cp,n,p,c,w,x,bestx</span><br><span class="line">    cleft=c-cw</span><br><span class="line">    bound=cp</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=n <span class="keyword">and</span> w[i]&lt;=cleft):</span><br><span class="line">        cleft-=w[i]</span><br><span class="line">        bound+=p[i]</span><br><span class="line">        i+=<span class="number">1</span></span><br><span class="line">    <span class="comment">#贪心</span></span><br><span class="line">    <span class="keyword">if</span>(i&lt;=n):</span><br><span class="line">        bound+=p[i]*cleft/w[i]</span><br><span class="line">    <span class="keyword">return</span> bound </span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">backtrack</span>(<span class="params">i</span>):</span></span><br><span class="line">    <span class="keyword">global</span> bestp,cw,cp,n,p,c,w,x,bestx</span><br><span class="line">    <span class="comment">#到达叶结点</span></span><br><span class="line">    <span class="keyword">if</span>(i&gt;n):</span><br><span class="line">        <span class="keyword">if</span>(cp&gt;bestp):</span><br><span class="line">            <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>):</span><br><span class="line">                bestx[j]=x[j]</span><br><span class="line">        bestp=cp</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="keyword">if</span>(cw+w[i]&lt;c):</span><br><span class="line">        x[i]=<span class="number">1</span></span><br><span class="line">        cw+=w[i]</span><br><span class="line">        cp+=p[i]</span><br><span class="line">        backtrack(i+<span class="number">1</span>)</span><br><span class="line">        cp-=p[i]</span><br><span class="line">        cw-=w[i]</span><br><span class="line">    <span class="keyword">if</span>(bound(i+<span class="number">1</span>)&gt;bestp):</span><br><span class="line">        x[i]=<span class="number">0</span></span><br><span class="line">        backtrack(i+<span class="number">1</span>)</span><br><span class="line">    </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    <span class="keyword">global</span> bestp,cw,cp,n,p,c,w,x,bestx</span><br><span class="line">    pp=<span class="built_in">input</span>(<span class="string">&quot;Please input the price of each items.(eg:1 2 3 4 5)\n&quot;</span>).split()</span><br><span class="line">    ww=<span class="built_in">input</span>(<span class="string">&quot;Please input the weight of each items.(eg:1 2 3 4 5)\n&quot;</span>).split()</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">len</span>(pp)!=<span class="built_in">len</span>(ww)):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;您的输入长度不一致！&quot;</span>)</span><br><span class="line">    n=<span class="built_in">len</span>(pp)</span><br><span class="line">    c=<span class="built_in">float</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the size of bag:\n&quot;</span>))</span><br><span class="line">    cw=<span class="number">0</span>        <span class="comment">#当前重量</span></span><br><span class="line">    cp=<span class="number">0</span>        <span class="comment">#当前价值</span></span><br><span class="line">    bestp=<span class="number">0</span>     <span class="comment">#当前最优价值</span></span><br><span class="line">    x=[<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n+<span class="number">1</span>)]       <span class="comment">#初始化临时选择方案</span></span><br><span class="line">    bestx=x[:]                      <span class="comment">#初始化最优选择方案</span></span><br><span class="line">    p=[<span class="number">0</span>]       <span class="comment">#价值列表</span></span><br><span class="line">    w=[<span class="number">0</span>]       <span class="comment">#重量列表</span></span><br><span class="line">    <span class="comment">#单位重量价值</span></span><br><span class="line">    <span class="comment">#初始化</span></span><br><span class="line">    q=[Q(<span class="number">0</span>,<span class="number">0</span>) <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n)]     </span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        pp[i]=<span class="built_in">float</span>(pp[i])</span><br><span class="line">        ww[i]=<span class="built_in">float</span>(ww[i])</span><br><span class="line">        q[i].d=pp[i]/ww[i]</span><br><span class="line">        q[i].<span class="built_in">id</span>=i</span><br><span class="line">    q=<span class="built_in">sorted</span>(q,key=<span class="keyword">lambda</span> x:x.d)[::-<span class="number">1</span>]                 <span class="comment">#从大到小排序</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        p.append(pp[q[i].<span class="built_in">id</span>])</span><br><span class="line">        w.append(ww[q[i].<span class="built_in">id</span>])</span><br><span class="line">    <span class="comment">#回溯</span></span><br><span class="line">    backtrack(<span class="number">1</span>)</span><br><span class="line">    <span class="comment">#打印输出</span></span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;Max price:&quot;</span>,bestp,<span class="string">&quot;包括：&quot;</span>)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(bestx)):</span><br><span class="line">        <span class="keyword">if</span>(bestx[i]==<span class="number">1</span>):</span><br><span class="line">            <span class="built_in">print</span>(<span class="string">f&quot;第<span class="subst">&#123;q[i-<span class="number">1</span>].<span class="built_in">id</span>+<span class="number">1</span>&#125;</span>个,价值：<span class="subst">&#123;pp[q[i-<span class="number">1</span>].<span class="built_in">id</span>]&#125;</span>,重量：<span class="subst">&#123;ww[q[i-<span class="number">1</span>].<span class="built_in">id</span>]&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h1 id="第六章-分支限界法"><a href="#第六章-分支限界法" class="headerlink" title="第六章 分支限界法"></a>第六章 分支限界法</h1><ul><li>分支限界法以<code>广度优先</code>或以<code>最小耗费(最大效益)优先</code>的方式搜索解空间树。其搜索策略是：在扩展结点处，先生成其所有儿子结点，然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一格活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中，选择一个最有利的结点作为扩展结点，使搜索朝着解空间上最优解的分支推进，以便尽快找出一个最优解。</li><li>常见两种分支限界法：①队列式（FIFO/LIFO）分支限界法②优先队列式分支限界法</li><li>与回溯法对比：<ul><li>（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。</li><li>（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。<br><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MoPuFI.png" alt="MoPuFI.png"></li></ul></li></ul><h2 id="6-5-0-1背包问题"><a href="#6-5-0-1背包问题" class="headerlink" title="6.5 0-1背包问题"></a>6.5 0-1背包问题</h2><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Q</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,_id,qq</span>):</span></span><br><span class="line">        self.<span class="built_in">id</span>=_<span class="built_in">id</span></span><br><span class="line">        self.d=qq</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BBnode</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,par,ch</span>):</span></span><br><span class="line">        self.par=par</span><br><span class="line">        self.ch=ch</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">HeapNode</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,bNode,up,pp,ww,lev</span>):</span></span><br><span class="line">        self.liveNode=bNode</span><br><span class="line">        self.up=up</span><br><span class="line">        self.p=pp</span><br><span class="line">        self.w=ww</span><br><span class="line">        self.lev=lev</span><br><span class="line"></span><br><span class="line"><span class="comment">#插入队列</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">addlivenode</span>(<span class="params">heap,up,pp,ww,lev,par,ch</span>):</span></span><br><span class="line">    b=BBnode(par,ch)</span><br><span class="line">    node=HeapNode(b,up,pp,ww,lev)</span><br><span class="line">    heap.append(node)</span><br><span class="line"></span><br><span class="line"><span class="comment">#上界函数，贪心</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bound</span>(<span class="params">i</span>):</span></span><br><span class="line">    <span class="keyword">global</span> cw,cp,n,p,c,w</span><br><span class="line">    cleft=c-cw</span><br><span class="line">    bound=cp</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=n <span class="keyword">and</span> w[i]&lt;=cleft):</span><br><span class="line">        cleft-=w[i]</span><br><span class="line">        bound+=p[i]</span><br><span class="line">        i+=<span class="number">1</span></span><br><span class="line">    </span><br><span class="line">    <span class="keyword">if</span>(i&lt;=n):</span><br><span class="line">        bound+=p[i]*cleft/w[i]</span><br><span class="line">    <span class="keyword">return</span> bound</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">knapsack</span>():</span></span><br><span class="line">    <span class="keyword">global</span> bestp,cw,cp,n,p,c,w,bestx</span><br><span class="line">    i=<span class="number">1</span></span><br><span class="line">    up=bound(i)</span><br><span class="line">    heap=[]</span><br><span class="line">    cnode=BBnode(<span class="literal">None</span>,<span class="literal">None</span>)</span><br><span class="line">    <span class="keyword">while</span>(i!=n+<span class="number">1</span>):</span><br><span class="line">        <span class="comment">#左孩子</span></span><br><span class="line">        cleft=cw+w[i]</span><br><span class="line">        <span class="keyword">if</span>(cleft&lt;c):</span><br><span class="line">            <span class="keyword">if</span>(cp+p[i]&gt;bestp):</span><br><span class="line">                bestp=cp+p[i]</span><br><span class="line">            addlivenode(heap,up,cp+p[i],cw+w[i],i+<span class="number">1</span>,cnode,<span class="literal">True</span>)</span><br><span class="line">        <span class="comment">#右孩子</span></span><br><span class="line">        up=bound(i+<span class="number">1</span>)</span><br><span class="line">        <span class="keyword">if</span>(up&gt;=bestp):</span><br><span class="line">            addlivenode(heap,up,cp+p[i],cw+w[i],i+<span class="number">1</span>,cnode,<span class="literal">False</span>)</span><br><span class="line">        <span class="comment">#取下一扩展结点</span></span><br><span class="line">        node=heap.pop(<span class="number">0</span>)</span><br><span class="line">        <span class="comment">#更新数据</span></span><br><span class="line">        cnode=node.liveNode</span><br><span class="line">        cw=node.w</span><br><span class="line">        cp=node.p</span><br><span class="line">        up=node.up</span><br><span class="line">        i=node.lev</span><br><span class="line"></span><br><span class="line">    <span class="comment">#最优解</span></span><br><span class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>)[::-<span class="number">1</span>]:</span><br><span class="line">        bestx[j]=<span class="number">1</span> <span class="keyword">if</span> cnode.ch==<span class="literal">True</span> <span class="keyword">else</span> <span class="number">0</span></span><br><span class="line">        cnode=cnode.par</span><br></pre></td></tr></table></figure><p>实现</p><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 0-1背包问题（分支限界法）</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Q</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,_id,qq</span>):</span></span><br><span class="line">        self.<span class="built_in">id</span>=_<span class="built_in">id</span></span><br><span class="line">        self.d=qq</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">BBnode</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,par,ch</span>):</span></span><br><span class="line">        self.par=par</span><br><span class="line">        self.ch=ch</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">HeapNode</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,bNode,up,pp,ww,lev</span>):</span></span><br><span class="line">        self.liveNode=bNode</span><br><span class="line">        self.up=up</span><br><span class="line">        self.p=pp</span><br><span class="line">        self.w=ww</span><br><span class="line">        self.lev=lev</span><br><span class="line"></span><br><span class="line"><span class="comment">#插入队列</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">addlivenode</span>(<span class="params">heap,up,pp,ww,lev,par,ch</span>):</span></span><br><span class="line">    b=BBnode(par,ch)</span><br><span class="line">    node=HeapNode(b,up,pp,ww,lev)</span><br><span class="line">    heap.append(node)</span><br><span class="line"></span><br><span class="line"><span class="comment">#上界函数，贪心</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bound</span>(<span class="params">i</span>):</span></span><br><span class="line">    <span class="keyword">global</span> cw,cp,n,p,c,w</span><br><span class="line">    cleft=c-cw</span><br><span class="line">    bound=cp</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=n <span class="keyword">and</span> w[i]&lt;=cleft):</span><br><span class="line">        cleft-=w[i]</span><br><span class="line">        bound+=p[i]</span><br><span class="line">        i+=<span class="number">1</span></span><br><span class="line">    </span><br><span class="line">    <span class="keyword">if</span>(i&lt;=n):</span><br><span class="line">        bound+=p[i]*cleft/w[i]</span><br><span class="line">    <span class="keyword">return</span> bound</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">knapsack</span>():</span></span><br><span class="line">    <span class="keyword">global</span> bestp,cw,cp,n,p,c,w,bestx</span><br><span class="line">    i=<span class="number">1</span></span><br><span class="line">    up=bound(i)</span><br><span class="line">    heap=[]</span><br><span class="line">    cnode=BBnode(<span class="literal">None</span>,<span class="literal">None</span>)</span><br><span class="line">    <span class="keyword">while</span>(i!=n+<span class="number">1</span>):</span><br><span class="line">        <span class="comment">#左孩子</span></span><br><span class="line">        cleft=cw+w[i]</span><br><span class="line">        <span class="keyword">if</span>(cleft&lt;c):</span><br><span class="line">            <span class="keyword">if</span>(cp+p[i]&gt;bestp):</span><br><span class="line">                bestp=cp+p[i]</span><br><span class="line">            addlivenode(heap,up,cp+p[i],cw+w[i],i+<span class="number">1</span>,cnode,<span class="literal">True</span>)</span><br><span class="line">        <span class="comment">#右孩子</span></span><br><span class="line">        up=bound(i+<span class="number">1</span>)</span><br><span class="line">        <span class="keyword">if</span>(up&gt;=bestp):</span><br><span class="line">            addlivenode(heap,up,cp+p[i],cw+w[i],i+<span class="number">1</span>,cnode,<span class="literal">False</span>)</span><br><span class="line">        <span class="comment">#取下一扩展结点</span></span><br><span class="line">        node=heap.pop(<span class="number">0</span>)</span><br><span class="line">        <span class="comment">#更新数据</span></span><br><span class="line">        cnode=node.liveNode</span><br><span class="line">        cw=node.w</span><br><span class="line">        cp=node.p</span><br><span class="line">        up=node.up</span><br><span class="line">        i=node.lev</span><br><span class="line"></span><br><span class="line">    <span class="comment">#最优解</span></span><br><span class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>)[::-<span class="number">1</span>]:</span><br><span class="line">        bestx[j]=<span class="number">1</span> <span class="keyword">if</span> cnode.ch==<span class="literal">True</span> <span class="keyword">else</span> <span class="number">0</span></span><br><span class="line">        cnode=cnode.par</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    <span class="keyword">global</span> bestp,cw,cp,n,p,c,w,bestx</span><br><span class="line">    <span class="comment">#输入</span></span><br><span class="line">    pp=<span class="built_in">input</span>(<span class="string">&quot;Please input the price of each items.(eg:1 2 3 4 5)\n&quot;</span>).split()</span><br><span class="line">    ww=<span class="built_in">input</span>(<span class="string">&quot;Please input the weight of each items.(eg:1 2 3 4 5)\n&quot;</span>).split()</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">len</span>(pp)!=<span class="built_in">len</span>(ww)):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;您的输入长度不一致！&quot;</span>)</span><br><span class="line">    n=<span class="built_in">len</span>(pp)</span><br><span class="line">    c=<span class="built_in">float</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the size of bag:\n&quot;</span>))</span><br><span class="line">    cw=<span class="number">0</span>        <span class="comment">#当前重量</span></span><br><span class="line">    cp=<span class="number">0</span>        <span class="comment">#当前价值</span></span><br><span class="line">    bestp=<span class="number">0</span>     <span class="comment">#当前最优价值</span></span><br><span class="line">    bestx=[<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n+<span class="number">1</span>)]   <span class="comment">#最优解初始化</span></span><br><span class="line">    p=[<span class="number">0</span>]</span><br><span class="line">    w=[<span class="number">0</span>]</span><br><span class="line">    q=[Q(<span class="number">0</span>,<span class="number">0</span>) <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n)]     <span class="comment">#单位重量价值</span></span><br><span class="line">    allp=<span class="number">0</span>    <span class="comment">#总价值</span></span><br><span class="line">    allw=<span class="number">0</span>    <span class="comment">#总重量</span></span><br><span class="line">    <span class="comment">#单位重量价值列表</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        pp[i]=<span class="built_in">float</span>(pp[i])</span><br><span class="line">        ww[i]=<span class="built_in">float</span>(ww[i])</span><br><span class="line">        allp+=pp[i]</span><br><span class="line">        allw+=ww[i]</span><br><span class="line">        q[i].d=pp[i]/ww[i]</span><br><span class="line">        q[i].<span class="built_in">id</span>=i</span><br><span class="line">    q=<span class="built_in">sorted</span>(q,key=<span class="keyword">lambda</span> x:x.d)[::-<span class="number">1</span>]                 <span class="comment">#从大到小排序</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        p.append(pp[q[i].<span class="built_in">id</span>])</span><br><span class="line">        w.append(ww[q[i].<span class="built_in">id</span>])</span><br><span class="line">    <span class="comment">#如果能直接全装</span></span><br><span class="line">    <span class="keyword">if</span>(allw&lt;c):</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">f&quot;All in! Total price is <span class="subst">&#123;allp&#125;</span>!&quot;</span>)</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line"></span><br><span class="line">    knapsack()</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">&quot;Max price:&quot;</span>,bestp,<span class="string">&quot;包括：&quot;</span>)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(bestx)):</span><br><span class="line">        <span class="keyword">if</span>(bestx[i]==<span class="number">1</span>):</span><br><span class="line">            <span class="built_in">print</span>(<span class="string">f&quot;第<span class="subst">&#123;q[i-<span class="number">1</span>].<span class="built_in">id</span>+<span class="number">1</span>&#125;</span>个,价值：<span class="subst">&#123;pp[q[i-<span class="number">1</span>].<span class="built_in">id</span>]&#125;</span>,重量：<span class="subst">&#123;ww[q[i-<span class="number">1</span>].<span class="built_in">id</span>]&#125;</span>&quot;</span>)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法!出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h2 id="6-6-装载问题"><a href="#6-6-装载问题" class="headerlink" title="6.6 装载问题"></a>6.6 装载问题</h2><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"><span class="string">Copyright: Copyright (c) 2019</span></span><br><span class="line"><span class="string">Author: Justlovesmile</span></span><br><span class="line"><span class="string">Title: 装载问题（分支限界法）</span></span><br><span class="line"><span class="string">&quot;&quot;&quot;</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span>(<span class="params">self,parent,isleftchild,weight</span>):</span></span><br><span class="line">        self.parent=parent</span><br><span class="line">        self.islchild=isleftchild</span><br><span class="line">        self.weight=weight</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">maxloading</span>(<span class="params">c</span>):</span></span><br><span class="line">    <span class="keyword">global</span> w,bestx,bestw,r,cw,n</span><br><span class="line">    i=<span class="number">1</span></span><br><span class="line">    r-=w[i]</span><br><span class="line">    cnode=Node(<span class="literal">None</span>,<span class="literal">None</span>,-<span class="number">1</span>)    <span class="comment">#当前结点</span></span><br><span class="line">    q=[cnode]</span><br><span class="line">    <span class="keyword">while</span>(<span class="literal">True</span>):</span><br><span class="line">        <span class="comment">#左结点</span></span><br><span class="line">        cleft=cw+w[i]</span><br><span class="line">        <span class="keyword">if</span>(cleft&lt;=c):</span><br><span class="line">            enode=Node(cnode,<span class="literal">True</span>,cleft)</span><br><span class="line">            <span class="keyword">if</span>(cleft&gt;bestw):</span><br><span class="line">                bestw=cleft    </span><br><span class="line">                bestx=enode</span><br><span class="line">            <span class="keyword">if</span>(i&lt;n):</span><br><span class="line">                q.append(enode)</span><br><span class="line">            <span class="keyword">if</span>(i==n):</span><br><span class="line">                <span class="keyword">return</span>;</span><br><span class="line">        <span class="comment">#右结点</span></span><br><span class="line">        <span class="keyword">if</span>(cw+r&gt;bestw <span class="keyword">and</span> i&lt;n):</span><br><span class="line">            enode=Node(cnode,<span class="literal">False</span>,cw)</span><br><span class="line">            q.append(enode)</span><br><span class="line">        <span class="comment">#出队列</span></span><br><span class="line">        cnode=q.pop(<span class="number">0</span>)</span><br><span class="line">        cw=cnode.weight</span><br><span class="line">        <span class="keyword">if</span>(cw==-<span class="number">1</span>):</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">len</span>(q)==<span class="number">0</span>):</span><br><span class="line">                <span class="keyword">return</span> ;</span><br><span class="line">            q.append(Node(<span class="literal">None</span>,<span class="literal">None</span>,-<span class="number">1</span>))</span><br><span class="line">            cnode=q.pop(<span class="number">0</span>)</span><br><span class="line">            cw=cnode.weight</span><br><span class="line">            i+=<span class="number">1</span></span><br><span class="line">            r-=w[i]</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">main</span>():</span></span><br><span class="line">    <span class="keyword">global</span> w,bestx,bestw,r,cw,n</span><br><span class="line">    w=[<span class="number">0</span>]</span><br><span class="line">    m=<span class="built_in">input</span>(<span class="string">&quot;Please input the weight of each items:(eg:1 2 3 4 5)\n&quot;</span>).split()</span><br><span class="line">    n=<span class="built_in">len</span>(m)    <span class="comment">#物品数量</span></span><br><span class="line">    <span class="keyword">if</span>(n==<span class="number">0</span>):</span><br><span class="line">        <span class="keyword">raise</span> ValueError(<span class="string">&quot;物品数量不能为空！&quot;</span>)</span><br><span class="line">    r=<span class="number">0</span>         <span class="comment">#剩余的物品容量</span></span><br><span class="line">    bestw,cw=<span class="number">0</span>,<span class="number">0</span></span><br><span class="line">    <span class="comment">#转换w类型并初始化r</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n):</span><br><span class="line">        w.append(<span class="built_in">int</span>(m[i]))</span><br><span class="line">        r+=w[i+<span class="number">1</span>]</span><br><span class="line">    allweight=r    <span class="comment">#总重量</span></span><br><span class="line">    x=[<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(n+<span class="number">1</span>)]</span><br><span class="line">    tx=[]</span><br><span class="line">    c1=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the size of No.1 ship:\n&quot;</span>))      <span class="comment">#第一艘船载重量</span></span><br><span class="line">    c2=<span class="built_in">int</span>(<span class="built_in">input</span>(<span class="string">&quot;Please input the size of No.2 ship:\n&quot;</span>))      <span class="comment">#第二艘船载重量</span></span><br><span class="line"></span><br><span class="line">    maxloading(c1)</span><br><span class="line">    <span class="keyword">if</span>(bestw+c2&lt;allweight):</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;不能由两艘船装完！&quot;</span>)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>)[::-<span class="number">1</span>]:</span><br><span class="line">        <span class="keyword">if</span>(bestx.islchild==<span class="literal">True</span>):</span><br><span class="line">            tx.append(<span class="number">1</span>)</span><br><span class="line">        <span class="keyword">elif</span>(bestx.islchild==<span class="literal">False</span>):</span><br><span class="line">            tx.append(<span class="number">0</span>)</span><br><span class="line">        bestx=bestx.parent</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="built_in">len</span>(tx)):</span><br><span class="line">        x[i+<span class="number">1</span>]=tx[::-<span class="number">1</span>][i]</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">f&quot;第一艘船载重量<span class="subst">&#123;bestw&#125;</span>，包括：&quot;</span>)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">if</span>(x[i]==<span class="number">1</span>):</span><br><span class="line">            <span class="built_in">print</span>(<span class="string">f&quot;第<span class="subst">&#123;i&#125;</span>个集装箱&quot;</span>)</span><br><span class="line">    <span class="built_in">print</span>(<span class="string">f&quot;第二艘船载重量<span class="subst">&#123;allweight-bestw&#125;</span>,包括：&quot;</span>)</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> <span class="built_in">range</span>(<span class="number">1</span>,n+<span class="number">1</span>):</span><br><span class="line">        <span class="keyword">if</span>(x[i]==<span class="number">0</span>):</span><br><span class="line">            <span class="built_in">print</span>(<span class="string">f&quot;第<span class="subst">&#123;i&#125;</span>个集装箱&quot;</span>)    </span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    <span class="keyword">try</span>:</span><br><span class="line">        main()</span><br><span class="line">    <span class="keyword">except</span> Exception <span class="keyword">as</span> e:</span><br><span class="line">        <span class="built_in">print</span>(<span class="string">&quot;您的输入不合法！出错信息如下：&quot;</span>)</span><br><span class="line">        <span class="built_in">print</span>(e)</span><br></pre></td></tr></table></figure><h1 style="text-align:center">知识点整理</h1><ul><li><p>算法的特征：<code>输入，输出，确定性，有限性</code></p></li><li><p>θ记号在算法复杂性的表示法中表示<code>紧致界</code></p></li><li><p>由分治法产生的子问题往往是<code>原问题的较小模式</code>，这就为使用<code>递归</code>提供了方便</p></li><li><p>建立计算模型的目的：<code>为了使问题的计算复杂性分析有一个共同的客观尺度</code></p></li><li><p>基本计算模型：<code>RAM</code>,<code>RASP</code>,<code>TM</code></p></li><li><p>拉斯维加斯算法找到的解一定是<code>正确</code>的</p></li><li><p>贪心算法常采用<code>自顶向下</code>的方式求解最优解</p></li><li><p>采用高级语言的主要好处：</p><blockquote><p>①更接近算法语言，易学，易掌握②提供了结构化程序设计的环境和工具，使得设计出的程序可读性高，可维护性强，可靠性高③不依赖于机器语言，因此写出的程序可移植性好，重用率高③自动化程度高，开发周期短，程序员可以集中精力从事更重要的创造性劳动，提高程序质量</p></blockquote></li><li><p>贪心算法的特点：</p><blockquote><p>①不能保证最后求得的解是最优的②策略易发现，运用简单，被广泛运用③策略多样，结果也多样④常用到辅助算法：排序</p></blockquote></li><li><p><code>平衡子问题</code>思想：通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同</p></li><li><p>Prim算法采用<code>贪心策略</code>求解<code>最小生成树问题</code>，其时间复杂度是O(n^2)。</p></li><li><p>动态规划算法适用于解具有<code>某种最优性质</code>的问题。</p></li><li><p>贪心算法做出的选择只是适用于在某种意义上的<code>局部最优</code>选择</p></li><li><p>在动态规划算法中，通常不同子问题的个数随问题规模呈<code>多项式</code>级增长</p></li><li><p>动态规划是解决<code>多阶段决策过程</code>的最优化问题</p></li><li><p><code>选择能产生最优解的贪心准则</code>是设计贪心算法的核心问题</p></li><li><p>分支限界法常以<code>广度优先</code>或以<code>最小耗费（最大效益）优先</code>的方式搜索问题的解空间树</p></li><li><p>为什么用分治法设计的算法一般有递归调用？因为子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归</p></li><li><p>请简述分支限界法找最优解比回溯法高的原因：在分支限界法中，每一个点只有一次机会称为扩展结点。</p></li><li><p>回溯法的算法框架按照问题的解空间一般分为<code>子集树</code>算法框架（如解0-1背包问题）和<code>排列树</code>算法框架（如解批处理作业调度问题）</p></li><li><p><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MIEmhn.png" alt="MIEmhn.png"></p></li><li><p>常见的多项式阶：<code>O(1) &lt; O(logn) &lt; O(n) &lt; O(nlogn) &lt; O(n^2) &lt; O(n^3) &lt; O(2^n) &lt; O(n!) &lt; O(n^n)</code></p></li><li><p>回溯和分支限界：</p><ul><li>相同点：都是以构造一颗状态空间树为基础的，树的结点反映了对一部分解所作的特定选择</li><li>不同点：①他们处理的问题类型不同，回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。②生成状态空间树的顺序不同③对节点存储的常用数据结构以及节点存储特性也各不相同，除由搜索方式决定的不同的存储结构外，分支限界法通常需要存储一些额外的信息以利于进一步地展开搜索</li></ul></li><li><p><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MoFWQK.png" alt="MoFWQK.png"></p></li><li><p><img src="" data-lazy-src="https://s2.ax1x.com/2019/11/21/MoFHJI.png" alt="MoFHJI.png"></p></li><li><p>NP问题是指还未被证明是否存在多项式算法能够解决的问题，而其中NP完全问题又是最有可能不是P问题的问题类型。所有的NP问题都可以用多项式时间划归到他们中的一个。所以显然NP完全的问题具有如下性质：它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。</p></li></ul></article><div class="post-reward"><div class="reward-button"><i class="fas fa-hamburger"></i> 打赏作者</div><div class="reward-main"><ul class="reward-all"><ul class="reward-group"><li class="reward-item"><a href="/img/wechat.jpg" target="_blank"><img class="post-qr-code-img" src="" data-lazy-src="/img/wechat.jpg" alt="微信"></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="/img/alipay.jpg" target="_blank"><img class="post-qr-code-img" src="" data-lazy-src="/img/alipay.jpg" alt="支付宝"></a><div class="post-qr-code-desc">支付宝</div></li></ul><a class="reward-main-btn" href="/donate"><div class="reward-text">赞赏者名单</div><div class="reward-dec">因为你们的支持让我意识到写文章的价值🙏</div></a></ul></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E7%AE%97%E6%B3%95/">算法</a><a class="post-meta__tags" href="/tags/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">学习笔记</a><a class="post-meta__tags" href="/tags/%E5%A4%A7%E5%AD%A6%E8%AF%BE%E7%A8%8B/">大学课程</a></div><div class="post_share"><div class="social-share" data-image="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/H21b5f6b8496141a1979a33666e1074d9x.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload='this.media="all"'><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer="defer"></script></div></div><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-info">大学课程 | 《算法分析与设计》笔记</span></div><div class="post-copyright__type"><span class="post-copyright-info"><a href="https://blog.justlovesmile.top/posts/16050.html">https://blog.justlovesmile.top/posts/16050.html</a></span></div><div class="post-copyright__notice"><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank" rel="external nofollow noopener noreferrer">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://blog.justlovesmile.top" target="_blank">Justlovesmile's BLOG</a>！</span></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/posts/10024.html"><img class="prev-cover" src="" data-lazy-src="https://s2.ax1x.com/2019/12/09/Q0YD61.jpg" onerror='onerror=null,src="/img/404.jpg"' alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">学习笔记 | Review card for MJ</div></div></a></div><div class="next-post pull-right"><a href="/posts/5271.html"><img class="next-cover" src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/lol2019.jpg" onerror='onerror=null,src="/img/404.jpg"' alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">Python爬虫 | 如何快速获取LOL英雄皮肤高清图片</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/posts/4582.html" title="学习笔记 | 《算法导论》之从入门到放弃（4）"><img class="cover" src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/keyboard.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-11-02</div><div class="title">学习笔记 | 《算法导论》之从入门到放弃（4）</div></div></a></div><div><a href="/posts/54183.html" title="学习笔记 | 《算法导论》之从入门到放弃（3）"><img class="cover" src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/sight.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-10-11</div><div class="title">学习笔记 | 《算法导论》之从入门到放弃（3）</div></div></a></div><div><a href="/posts/4966.html" title="学习笔记 | 《算法导论》之从入门到放弃（2）"><img class="cover" src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/type.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-09-23</div><div class="title">学习笔记 | 《算法导论》之从入门到放弃（2）</div></div></a></div><div><a href="/posts/4646.html" title="学习笔记 | 《算法导论》之从入门到放弃（1）"><img class="cover" src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/robotandlight.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2019-09-19</div><div class="title">学习笔记 | 《算法导论》之从入门到放弃（1）</div></div></a></div><div><a href="/posts/651e6a0b.html" title="大学课程 | 计算机系统结构精简知识点"><img class="cover" src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/1584111180-soft.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-09-08</div><div class="title">大学课程 | 计算机系统结构精简知识点</div></div></a></div><div><a href="/posts/43666.html" title="大学课程 | 《微机原理与接口技术》笔记"><img class="cover" src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/1584110553-u34116618882606377503fm11gp0.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-09-05</div><div class="title">大学课程 | 《微机原理与接口技术》笔记</div></div></a></div></div></div><hr><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i> <span>评论</span></div></div><div class="comment-wrap"><div><div id="twikoo-wrap"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="" data-lazy-src="/img/avatar.jpg" onerror='this.onerror=null,this.src="/img/friend_404.gif"' alt="avatar"></div><div class="author-info__name">Justlovesmile</div><div class="author-info__description">一个计算机专业学生的个人博客，记录着学习笔记和生活中的思考，期待着和所有人相遇</div></div><div class="card-info-data is-center"><div class="card-info-data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">75</div></a></div><div class="card-info-data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">69</div></a></div><div class="card-info-data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">6</div></a></div></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content"><p>不定时更新博客，欢迎交换<a href="/friends/"><strong>友链</strong></a>...</p><div class="twopeople"><div class="container" style="height:200px"><canvas class="illo" width="800" height="800" style="max-width:200px;max-height:200px;touch-action:none;width:640px;height:640px"></canvas></div><script src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/js/twopeople1.js"></script><script src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/js/zdog.dist.js"></script><script id="rendered-js" src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/js/twopeople.js"></script><style>.twopeople{margin:0;align-items:center;justify-content:center;text-align:center}canvas{display:block;margin:0 auto;cursor:move}</style></div><div style="text-align:center"><a href="https://www.foreverblog.cn/" target="_blank" rel="external nofollow noopener noreferrer"><img src="" data-lazy-src="https://img.foreverblog.cn/logo_en_default.png" alt="foreverblog" style="width:auto;height:16px"></a></div></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link"><span class="toc-text">笔记总结</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E4%B8%80%E7%AB%A0-%E7%AE%97%E6%B3%95%E5%BC%95%E8%AE%BA"><span class="toc-text">第一章 算法引论</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-1-%E7%AE%97%E6%B3%95%E4%B8%8E%E7%A8%8B%E5%BA%8F"><span class="toc-text">1.1 算法与程序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-2-%E8%A1%A8%E8%BE%BE%E7%AE%97%E6%B3%95%E7%9A%84%E6%8A%BD%E8%B1%A1%E6%9C%BA%E5%88%B6"><span class="toc-text">1.2 表达算法的抽象机制</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-3-%E6%8F%8F%E8%BF%B0%E7%AE%97%E6%B3%95"><span class="toc-text">1.3 描述算法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#1-4-%E7%AE%97%E6%B3%95%E5%A4%8D%E6%9D%82%E6%80%A7%E5%88%86%E6%9E%90"><span class="toc-text">1.4 算法复杂性分析</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E4%BA%8C%E7%AB%A0-%E9%80%92%E5%BD%92%E4%B8%8E%E5%88%86%E6%B2%BB%E7%AD%96%E7%95%A5"><span class="toc-text">第二章 递归与分治策略</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#2-1-%E9%80%92%E5%BD%92%E7%9A%84%E6%A6%82%E5%BF%B5"><span class="toc-text">2.1 递归的概念</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-2-%E5%88%86%E6%B2%BB%E6%B3%95%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%80%9D%E6%83%B3"><span class="toc-text">2.2 分治法的基本思想</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-3-%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E6%8A%80%E6%9C%AF"><span class="toc-text">2.3 二分搜索技术</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-4-%E5%A4%A7%E6%95%B4%E6%95%B0%E4%B9%98%E6%B3%95"><span class="toc-text">2.4 大整数乘法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-5-Strassen%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95"><span class="toc-text">2.5 Strassen矩阵乘法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-7-%E5%90%88%E5%B9%B6%E6%8E%92%E5%BA%8F"><span class="toc-text">2.7 合并排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-8-%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F"><span class="toc-text">2.8 快速排序</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-9-%E7%BA%BF%E6%80%A7%E6%97%B6%E9%97%B4%E9%80%89%E6%8B%A9"><span class="toc-text">2.9 线性时间选择</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-10-%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9%E9%97%AE%E9%A2%98"><span class="toc-text">2.10 最近点对问题</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E4%B8%89%E7%AB%A0-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92"><span class="toc-text">第三章 动态规划</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#3-1-%E7%9F%A9%E9%98%B5%E8%BF%9E%E4%B9%98%E9%97%AE%E9%A2%98"><span class="toc-text">3.1 矩阵连乘问题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-3-%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-text">3.3 最长公共子序列</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-4-%E5%87%B8%E5%A4%9A%E8%BE%B9%E5%BD%A2%E6%9C%80%E4%BC%98%E4%B8%89%E8%A7%92%E5%89%96%E5%88%86"><span class="toc-text">3.4 凸多边形最优三角剖分</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-9-0-1%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">3.9 0-1背包问题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-10-%E6%9C%80%E4%BC%98%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91"><span class="toc-text">3.10 最优二叉搜索树</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E5%9B%9B%E7%AB%A0-%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95"><span class="toc-text">第四章 贪心算法</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#4-2-%E6%B4%BB%E5%8A%A8%E5%AE%89%E6%8E%92%E9%97%AE%E9%A2%98"><span class="toc-text">4.2 活动安排问题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-3-%E6%9C%80%E4%BC%98%E8%A3%85%E8%BD%BD%E9%97%AE%E9%A2%98"><span class="toc-text">4.3 最优装载问题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-4-%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81"><span class="toc-text">4.4 哈夫曼编码</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-5-%E5%8D%95%E6%BA%90%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84"><span class="toc-text">4.5 单源最短路径</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-6-%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91"><span class="toc-text">4.6 最小生成树</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E4%BA%94%E7%AB%A0-%E5%9B%9E%E6%BA%AF%E6%B3%95"><span class="toc-text">第五章 回溯法</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#5-2-%E8%A3%85%E8%BD%BD%E9%97%AE%E9%A2%98"><span class="toc-text">5.2 装载问题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-6-0-1%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">5.6 0-1背包问题</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E7%AC%AC%E5%85%AD%E7%AB%A0-%E5%88%86%E6%94%AF%E9%99%90%E7%95%8C%E6%B3%95"><span class="toc-text">第六章 分支限界法</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#6-5-0-1%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-text">6.5 0-1背包问题</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#6-6-%E8%A3%85%E8%BD%BD%E9%97%AE%E9%A2%98"><span class="toc-text">6.6 装载问题</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link"><span class="toc-text">知识点整理</span></a></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/posts/56b0563d.html" title="Hexo博客 | 如何让Butterfly主题导航栏居中"><img src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN2/post/20220315095300.png" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="Hexo博客 | 如何让Butterfly主题导航栏居中"></a><div class="content"><a class="title" href="/posts/56b0563d.html" title="Hexo博客 | 如何让Butterfly主题导航栏居中">Hexo博客 | 如何让Butterfly主题导航栏居中</a><time datetime="2022-03-15T01:25:18.000Z" title="发表于 2022-03-15 09:25:18">2022-03-15</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/bb608df3.html" title="目标检测 | RetinaNet，经典单阶段Anchor-Based目标检测模型"><img src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN2/post/20220314113659.png" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="目标检测 | RetinaNet，经典单阶段Anchor-Based目标检测模型"></a><div class="content"><a class="title" href="/posts/bb608df3.html" title="目标检测 | RetinaNet，经典单阶段Anchor-Based目标检测模型">目标检测 | RetinaNet，经典单阶段Anchor-Based目标检测模型</a><time datetime="2022-03-14T03:26:21.000Z" title="发表于 2022-03-14 11:26:21">2022-03-14</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/fc798de3.html" title="目标检测 | Faster R-CNN，经典两阶段检测模型"><img src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN2/post/20220312220823.png" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="目标检测 | Faster R-CNN，经典两阶段检测模型"></a><div class="content"><a class="title" href="/posts/fc798de3.html" title="目标检测 | Faster R-CNN，经典两阶段检测模型">目标检测 | Faster R-CNN，经典两阶段检测模型</a><time datetime="2022-03-12T13:59:01.000Z" title="发表于 2022-03-12 21:59:01">2022-03-12</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/d150f284.html" title="深度学习 | 小样本学习基础概念"><img src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN2/post/202201271037441.png" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="深度学习 | 小样本学习基础概念"></a><div class="content"><a class="title" href="/posts/d150f284.html" title="深度学习 | 小样本学习基础概念">深度学习 | 小样本学习基础概念</a><time datetime="2022-01-27T02:24:38.000Z" title="发表于 2022-01-27 10:24:38">2022-01-27</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/e05a9ab6.html" title="Jupyter Lab | 安装、配置、插件推荐、多用户使用教程"><img src="" data-lazy-src="https://cdn.jsdelivr.net/gh/Justlovesmile/CDN2/post/image-20211125175041150.png" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="Jupyter Lab | 安装、配置、插件推荐、多用户使用教程"></a><div class="content"><a class="title" href="/posts/e05a9ab6.html" title="Jupyter Lab | 安装、配置、插件推荐、多用户使用教程">Jupyter Lab | 安装、配置、插件推荐、多用户使用教程</a><time datetime="2021-11-25T09:38:43.000Z" title="发表于 2021-11-25 17:38:43">2021-11-25</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div id="footer_deal"><a class="social-icon" href="mailto:865717150@qq.com" target="_blank" title="Email" rel="external nofollow noopener noreferrer"><i class="fas fa-envelope"></i></a><a class="social-icon" href="https://blog.csdn.net/qq_43701912" target="_blank" title="CSDN" rel="external nofollow noopener noreferrer"><i class="iconfont icon-csdn1"></i></a><a class="social-icon" href="https://github.com/Justlovesmile" target="_blank" title="Github" rel="external nofollow noopener noreferrer"><i class="fab fa-github"></i></a><a class="social-icon" href="https://weibo.com/u/5252319712" target="_blank" title="微博" rel="external nofollow noopener noreferrer"><i class="fa fa-weibo"></i></a><a class="social-icon" href="https://space.bilibili.com/168738824" target="_blank" title="Bilibili" rel="external nofollow noopener noreferrer"><i class="fas iconfont icon-bilibili"></i></a></div><div id="mj-footer"><div class="footer-group"><h3 class="footer-title">关于</h3><div class="footer-links"><a class="footer-item" target="_blank" rel="external nofollow noopener noreferrer" href="https://www.justlovesmile.top/">个人主页</a><a class="footer-item" href="/donate/">赞赏博主</a><a class="footer-item" href="/update/">博客日志</a><a class="footer-item" href="/charts/">博客统计</a></div></div><div class="footer-group"><h3 class="footer-title">归档</h3><div class="footer-links"><a class="footer-item" href="/archives/">文章归档</a><a class="footer-item" href="/tags/">全部标签</a><a class="footer-item" href="/categories/">全部分类</a><a class="footer-item" href="/random/">随机文章</a></div></div><div class="footer-group"><h3 class="footer-title">导航</h3><div class="footer-links"><a class="footer-item" href="/guestbook/">博客留言</a><a class="footer-item" href="/friends/">友情链接</a><a class="footer-item" href="/fcircle/">友链订阅</a><a class="footer-item" href="/atom.xml">RSS订阅</a></div></div><div class="footer-group"><h3 class="footer-title">协议</h3><div class="footer-links"><a class="footer-item" href="/privacy/">隐私协议</a><a class="footer-item" href="/cookies/">Cookies</a><a class="footer-item" href="/cc/">版权协议</a></div></div></div><div id="footer-banner"><div class="footer-banner-links"><div class="footer-banner-left"><div id="footer-banner-tips">©2019 - 2022 By Justlovesmile</div></div><div class="footer-banner-right"><a class="footer-banner-link" target="_blank" rel="external nofollow noopener noreferrer" href="http://beian.miit.gov.cn/">蜀ICP备20004960号</a><a class="footer-banner-link" href="/update/">主题</a><a class="footer-banner-link" href="/about/">关于</a></div></div></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">本地搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i> <span>数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"></div></div><hr><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script defer="defer" src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox.umd.js"></script><script defer="defer" src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script defer="defer" src="https://cdn.jsdelivr.net/npm/vanilla-lazyload/dist/lazyload.iife.min.js"></script><script defer="defer" src="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.js"></script><script defer="defer" src="/js/search/local-search.js"></script><div class="js-pjax"><script>(()=>{const t=()=>{twikoo.init(Object.assign({el:"#twikoo-wrap",envId:"blog-comment-3gt33nkmf9f97e6e",region:"ap-shanghai",onCommentLoaded:function(){btf.loadLightbox(document.querySelectorAll("#twikoo .tk-content img:not(.vemoji)"))}},null))},o=()=>{"object"!=typeof twikoo?getScript("https://cdn.jsdelivr.net/npm/twikoo/dist/twikoo.all.min.js").then(t):setTimeout(t,0)};btf.loadComment(document.getElementById("twikoo-wrap"),o)})()</script></div><canvas id="universe"></canvas><script defer="defer">console.log("\n %c 欢迎来到Justlovesmile の Blog %c https://github.com/Justlovesmile %c https://blog.justlovesmile.top \n","color: #f9ed69; background: #252a34; padding:5px 0;","background: #3fc1c9; padding:5px 0;","background: #3fc1c9; padding:5px 0;")</script><script defer="defer" src="/js/rgbaster.min.js"></script><script defer="defer" src="/js/justlovesmile.js"></script><script>window.addEventListener("load",async()=>{navigator.serviceWorker.register("/js/sw-cdn.js?time="+(new Date).getTime()).then(async e=>{"true"!=window.localStorage.getItem("install")&&(window.localStorage.setItem("install","true"),setTimeout(()=>{window.location.search="?time="+(new Date).getTime()},1e3))}).catch(e=>{console.log("sw-cdn.js error")})})</script></div></body></html>